\chapter{数据结构}
\section{线性表}
线性表简称表,是零个或多个元素的有穷序列,通常可以表示成$k_0 ,k_1 , \ldots,k_{n-1} (n \geq 1)$
\begin{itemize}
    \item 表目:线性表中的元素(可包含多个数据项,记录)
    \item 索引(下标):i 称为表目 $k_i$ 的“索引”或“下标”
    \item 表的长度:线性表中所含元素的个数 n
    \item 空表:长度为零的线性表 ( n = 0 )
\end{itemize}
\textbf{线性表特点:}操作灵活,其长度可以增长、缩短。\\
二元组$R,K={a_0,a_1,\ldots,a_{n-1},R = {r}}$
\begin{itemize}
    \item 有一个唯一的开始结点,它没有前驱,有一个唯一的直接后继。
    \item  一个唯一的终止结点,它有一个唯一的直接前驱,而没有后继。
    \item 其它的结点皆称为内部结点,每一个内部结点都有且仅有一个唯一的直
          接有前驱,也有一个唯一的直接后继。
          $<a_i,a_{i+1}>a_i$ 是$a_{i+1}$ 的前驱,$a_{i+1}$是$a_i$ 的后继
    \item 前驱/后继关系r,具有 反对称性和传递性
\end{itemize}
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{ds_1.png}
    \caption{链式结构}
\end{figure}
\textbf{线性结构的特点}
\begin{itemize}
    \item 均匀性:虽然不同线性表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
    \item 有序性:各数据元素在线性表中都有自己的位置,且数据元素之间的相对位置是线性的。
\end{itemize}
\textbf{线性结构的分类}
\begin{itemize}
    \item 按复杂程度划分
          \begin{itemize}
              \item 简单的:线性表、栈、队列、散列表
              \item 高级的:广义表、多维数组、文件......
          \end{itemize}
    \item 按访问方式划分
          \begin{itemize}
              \item 直接访问型 (direct access)
              \item 顺序访问型 (sequential access)
              \item 目录索引型 (directory access)
          \end{itemize}
    \item 按操作划分
          \begin{itemize}
              \item 线性表
                    \begin{itemize}
                        \item 所有表目都是同一类型结点的线性表
                        \item  不限制操作形式
                        \item 根据存储的不同分为:顺序表,链表
                    \end{itemize}
              \item 栈（LIFO）插入和删除操作都限制在表的同一端进
              \item 队列（FIFO）插入操作在表的一端, 删除操作在另一端
          \end{itemize}
\end{itemize}
线性表的主要属性包括：
\begin{itemize}
    \item 主要属性包括
    \item 表头
    \item 线性表的长度
    \item 表头 (head)
    \item 表尾 (tail)
    \item 当前位置 (current position)
\end{itemize}
\textbf{顺序表}
\begin{itemize}
    \item 按索引值从小到大存放在一片相邻的连续区域
    \item 紧凑结构,存储密度为 1
\end{itemize}
\subsection{线性表实现方法的比较}
顺序表的主要优点
\begin{itemize}
    \item 没有使用指针,不用花费额外开销
    \item 线性表元素的读访问非常简洁便利
\end{itemize}
\textbf{链表的主要优点}：
\begin{itemize}
    \item  无需事先了解线性表的长度
    \item  允许线性表的长度动态变化
    \item  能够适应经常插入删除内部元素的情况
\end{itemize}
\textbf{总结}：
\begin{itemize}
    \item 顺序表是存储静态数据的不二选择
    \item 链表是存储动态变化数据的良方
\end{itemize}
\textbf{顺序表}
\begin{itemize}
    \item 插入、删除运算时间代价 O(n),查找则可常数时间完成
    \item 预先申请固定长度的连续空间
    \item 如果整个数组元素很满,则没有结构性存储开销
\end{itemize}
\textbf{链表}\\
\begin{itemize}
    \item 插入、删除运算时间代价 O(1),但找第i个元素运算时间代价 O(n)
    \item 存储利用指针,动态地按照需要为表中新的元素分配存储空间
    \item 每个元素都有结构性存储开销
\end{itemize}
\textbf{顺序表和链表存储密度}
n 表示线性表中当前元素的数目,
P 表示指针的存储单元大小(通常为 4 bytes)
E 表示数据元素的存储单元大小
D 表示可以在数组中存储的线性表元素的最大数目
\textbf{空间需求}
\begin{itemize}
    \item 顺序表的空间需求为 DE
    \item 链表的空间需求为 n(P + E)
\end{itemize}
n 的临界值,即 n > DE / (P+E)
\begin{itemize}
    \item n 越大,顺序表的空间效率就更高
    \item 如果P = E,则临界值为 n = D / 2
\end{itemize}
顺序表不适用的场合
\begin{itemize}
    \item  经常插入删除时,不宜使用顺序表
    \item  线性表的最大长度也是一个重要因素
\end{itemize}
\textbf{链表不适用的场合}
\begin{itemize}
    \item 当读操作比插入删除操作频率大时,不应选择链表
    \item 当指针的存储开销,和整个结点内容所占空间相比其比例较大时,应该慎重选择
\end{itemize}
\textbf{顺序表和链表的选择}\\
顺序表
\begin{itemize}
    \item 结点总数目大概可以估计
    \item 线性表中结点比较稳定(插入删除少)
    \item n > DE / (P + E)
\end{itemize}
\textbf{链表}\\
\begin{itemize}
    \item 结点数目无法预知
    \item 线性表中结点动态变化(插入删除多)
    \item n < DE / (P + E)>
\end{itemize}

\textbf{链表}
\begin{itemize}
    \item 单链
    \item 双链
    \item 循环链
\end{itemize}
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{linear_table}
    \caption{链接种类}
\end{figure}
栈（LIFO）插入和删除在表的同一端进行
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{linear_stack}
    \caption{栈的结构}
\end{figure}
\textbf{队列}：插入在表的一端，删除在表的另一端。

\textbf{线性表的类模板}
\cppfile[firstline=1,lastline=23]{code/datastruct/tree/include/list.h}
为了方便调试代码中添加了用于显示输出相关的成员函数。
\cppfile[firstline=24,lastline=71]{code/datastruct/tree/include/list.h}
\subsection{顺序表}
\textbf{顺序表：}也称向量,采用定长的一维数组存储结构

\textbf{主要特性：}
\begin{itemize}
    \item 元素的类型相同。
    \item 元素顺序地存储在连续存储空间中,每一个元素有唯一的索引值。
    \item 使用常数作为向量长度。
    \item 数组存储。
          \begin{itemize}
              \item  读写其元素很方便 ,通过下标即可指定位置。
              \item  只要确定了首地址,线性表中任意数据元素都可以随机存取。
          \end{itemize}
\end{itemize}
\begin{figure}[!htb]\label{fig:ds_13}
    \centering
    \includegraphics[width=\textwidth]{ds_13.png}
    \caption{线性表存储示意图}
\end{figure}
元素地址计算如$Loc(k_i)=Loc(k_0)+c\times i,c=sizeof(ELEM)$

\textbf{顺序表的类定义：}
\cppfile{code/DS/ex4/main.cpp}
顺序表插入示意\figref{fig:ds_13}
\begin{figure}[!htb]    \centering
    \includegraphics[width=\textwidth]{ds_13.png}
    \caption{顺序表插入示意图}
    \label{fig:ds_13}
\end{figure}
顺序表和插入代码：
\begin{cpp}
    // 设元素的类型为T, aList是存储顺序表的数组, maxSize是其最大长度;
    // p为新元素value的插入位置,插入成功则返回true, 否则返回false
    template <class T> bool arrList<T> :: insert (const int p, const T value) {
            int i;
            if (curLen >= maxSize) { // 检查顺序表是否溢出
                    cout << "The list is overflow"<< endl; return false;
                }
            if (p < 0 || p > curLen) { // 检查插入位置是否合法
                    cout << "Insertion point is illegal"<< endl; return false;
                }
            for (i = curLen; i > p; i--)
            aList[i] = aList[i-1];
            // 从表尾 curLen -1 起往右移动直到 p
            aList[p] = value;
            // 位置 p 处插入新元素
            curLen++;
            // 表的实际长度增 1
            return true;

        }
\end{cpp}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{ds_15.png}
    \caption{删除示意图}
    \label{fig:ds_15}
\end{figure}
\textbf{顺序表删除示意\figref{fig:ds_15}}
\begin{cpp}
    // 设元素的类型为 T;aList是存储顺序表的数组; p 为即将删除元素的位置
    // 删除成功则返回 true,否则返回 false
    template <class T>
    // 顺序表的元素类型为 T
    bool arrList<T> :: delete(const int p) {
            int i;
            if (curLen <= 0 ) {
                    // 检查顺序表是否为空
                    cout << " No element to delete \n"<< endl;
                    return false ;

                }
            if (p < 0 || p > curLen-1) { // 检查删除位置是否合法
                    cout << "deletion is illegal\n"<< endl;
                    return false ;
                }
            for (i = p; i < curLen-1; i++)
            aList[i] = aList[i+1];
            // 从位置p开始每个元素左移直到 curLen
            curLen--;
            // 表的实际长度减1
            return true;

        }
\end{cpp}
顺序表插入时间代价$M_i=\frac{n}{2}$,删除时间代价$M_d=\frac{n-1}{2}$
\subsection{链表}
通过指针把它的一串存储结点链接成一个链,存储结点由两部分组成:
\begin{itemize}
    \item  数据域
    \item 指针域(后继地址)
\end{itemize}
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{ds_4.png}
    \caption{链表}
\end{figure}
\textbf{带头节点的单链表}

\begin{itemize}
    \item 整个单链表：head
    \item 第一个节点：head->next,head$\neq$NULL
    \item 空表判断：head->next == NULL,当前节点$a_1$:fence->next(curr隐含)
\end{itemize}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{ds_5.png}
    \caption{单链表}
\end{figure}
单链表的节点类型：
\cppfile[firstline=7,lastline=18]{code/datastruct/tree/src/LinkNode.cpp}
单链表的方法：
\begin{itemize}
    \item 创建链表。
    \item 找到单链表中的某一个元素。
    \item 遍历链表。
    \item 判断判断链表是否为空。
    \item 获取链表长度。
    \item 删除链表节点。
    \item 清除整个链表。
    \item 获取指定节点。
    \item 获取链表节点的值。
    \item 添加元素到链表中。
\end{itemize}
单链表的类定义：

\cppfile[firstline=20,lastline=45]{code/datastruct/tree/src/LinkNode.cpp}
查找单链表中第i个节点

\cppfile[firstline=46,lastline=62]{code/datastruct/tree/src/LinkNode.cpp}
\textbf{单链表的插入示意图：}
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{ds_5.png}
    \caption{单链表插入}
\end{figure}
\begin{enumerate}
    \item 创建新节点
    \item 新节点指向右边的节点
    \item 左边节点指向新节点
\end{enumerate}

\cppfile[firstline=84,lastline=103]{code/datastruct/tree/src/LinkNode.cpp}
\textbf{单链表的删除}

从链表中删除节点
\begin{enumerate}
    \item 用p指向元素x的节点的前驱结点
    \item 释放元素x的结点
    \item 释放x占据的空间
\end{enumerate}
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{ds_7.png}
    \caption{链表删除节点示意图}
\end{figure}
\begin{cpp}
    // 删除节点
    q = p->next;
    p->next = q->next;
    free(q);
\end{cpp}
删除节点的算法：
\cppfile[firstline=132,lastline=147]{code/datastruct/tree/src/LinkNode.cpp}
对一个结点操作,必先找到它,即用一个指针指向它。
\begin{itemize}
    \item 找单链表中任一结点,都必须从第一个点开始
          \begin{Textcode}
              p = head;
              while (没有到达) p = p->next;
          \end{Textcode}
    \item 单链表的时间复杂度
          \begin{itemize}
              \item 定位:O(n)
              \item 插入：O(x)+O(1)
              \item 删除：O(n)+O(1)
          \end{itemize}
\end{itemize}
单链表的next字段仅仅指向后继节点，不能有效的查找前去，反之亦然。添加指向前驱的指针
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{bi_linklistnode}
    \caption{双链节点示意图}
    \label{fig:bi_linklistnode}
\end{figure}
双链结构示意图如\figref{fig:bi_linklist}
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{bi_linklist}
    \caption{双链示意图}
    \label{fig:bi_linklist}
\end{figure}
双链节点和结构定义：
\begin{cpp}
    template <class T> class Link {
            public:
            T data;
            // 用于保存结点元素的内容
            Link<T> * next;
            // 指向后继结点的指针
            Link<T> *prev;
            // 指向前驱结点的指针
            Link(const T info, Link<T>* preValue = NULL, Link<T>* nextValue = NULL) {
                    // 给定值和前后指针的构造函数
                    data = info;
                    next = nextValue;
                    prev = preValue;

                }
            Link(Link<T>* preValue = NULL, Link<T>* nextValue = NULL) {
                    // 给定前后指针的构造函数
                    next = nextValue;
                    prev = preValue;

                }

        }
\end{cpp}
\begin{figure}[!ht]
    \centering
    \includegraphics[width=\textwidth]{ds_10.png}
    \caption{双链插入节点示意图}
\end{figure}
\figref{fig:ds_11}是删除节点的示意图
\begin{figure}[!ht]    \centering
    \includegraphics[width=\textwidth]{ds_11.png}
    \caption{双链删除节点}
    \label{fig:ds_11}
\end{figure}

\begin{cpp}
    p->prev->next=p->next
    p->next->prev=p->prev
    p->next=NULL
    p->prev=NULL
\end{cpp}
\textbf{循环链}

将单链表或者双链表的头尾结点链接起来,就是一个循，环链表，不增加额外存储花销,却给不少操作带来了方便， 从循环表中任一结点出发,都能访问到表中其他结点。循环链示意图如\figref{fig:ds_12}
\begin{figure}[!ht]    \centering
    \includegraphics[width=\textwidth]{ds_12.png}
    \caption{循环链示意图}
    \label{fig:ds_12}
\end{figure}
\textbf{链表的边界条件}

\begin{itemize}
    \item 几个特殊点的处理
          \begin{itemize}
              \item  头指针处理
              \item  非循环链表尾结点的指针域保持为 NULL
              \item  循环链表尾结点的指针回指头结点
          \end{itemize}
    \item 链表处理
          \begin{itemize}
              \item 空链表的特殊处理
              \item 插入或删除结点时指针勾链的顺序
              \item 指针移动的正确性
              \item 插入
              \item 查找或遍历
          \end{itemize}

\end{itemize}
\subsection{数据结构应用}
农夫过河，现在有农夫，羊，狼，人，菜。农夫每次能带一个物品过河，羊和狼，羊和菜不能在人不在的时候在同一边，输出过河方式。
\cppfile{code/STL/arith/main.cpp}
\section{创建基本的数据结构}
线性表相关
\subsection{顺序表}
顺序表要实现的功能有:
\begin{itemize}
    \item 清空顺序表(\cppinline{void clear()})
    \item 判断顺序表是否为空(\cppinline{void isEmpty()})
    \item 在顺序表尾部添加元素\cppinline{(bool append(const T value))}
    \item 在位置p删除元素\cppinline{(bool insert(const int p,const T value))}
    \item 获取值为value的索引(\cppinline{bool delete(const int p))}
    \item 获取位置p的元素\cppinline{value(bool getPos(int& p,const T value))}
    \item 设置位置p的元素\cppinline{(bool setValue(const int p,const T value));}
\end{itemize}

\subsection{单链表}
单链表数据结构包括数据域和指针域。数据域用来存储数据元素的值，指针域用来指向下一个节点。
\begin{cpp}
    typedef struct Node{
            int value;
            Node * next;
        }
\end{cpp}
单链表应该包含的功能:
\begin{itemize}
    \item 删除单链表中的一个元素
    \item 获取单链表中的一个元素
    \item 修改单链表中的一个元素
    \item 清除单链表
    \item 获取单链表的长度
\end{itemize}
\section{栈和队列}
栈 (Stack)：运算只在表的一端进行。 队列 (Queue)：运算只在表的两端进行。

栈的抽象数据类型
\begin{cpp}
    template <typename T>
    class Stack {
            public:                     //栈的运算集
            void clear();               //变为空栈
            bool push(const T item);    //item入栈,成功返回真,否则假
            bool pop(T& item);          //返回栈顶内容并弹出,成功返回真,否则假
            bool top(T& item);          //返回栈顶但不弹出,成功返回真,否则假
            bool isEmpty();             //若栈已空返回真
            bool isFull();              //若栈已满返回真
        };
\end{cpp}
顺序栈 (Array-based Stack)
\begin{itemize}
    \item 使用向量实现,本质上是顺序表的简化版
    \item 关键是确定哪一端作为栈顶
    \item 上溢 (Overflow)当栈中已经有maxsize个元素时,如果再做进栈
          运算,所产生的现象
          下溢 (Underflow) 对空栈进行出栈运算时所产生的现象,下溢问题
\end{itemize}
\textbf{链式栈(Linked Stack)}用单链表方式存储,其中指针的方向是从栈顶向下
链接
\textbf{压栈操作代码框架}\\
\begin{cpp}
    bool arrStack<T>::push(const T item) {
            if (top == mSize-1) {    // 栈已满
                    cout << "栈满溢出" << endl;
                    return false;
                } else {       // 新元素入栈并修改栈顶指针
                    st[++top] = item;
                    return true;
                }
        }
\end{cpp}
\textbf{栈顶操作代码框架}
\begin{cpp}
    bool arrStack<T>::pop(T & item) { // 出栈
            if (top == -1) {                  // 栈为空
                    cout << "栈为空,不能执行出栈操作"<< endl;
                    return false;
                } else {
                    item = st[top--]; // 返回栈顶,并缩减1
                    return true;
                }
        }
\end{cpp}
顺序栈的实现：
\cppfile{code/DS/ex7/Stack.hpp}
测试代码：
\cppfile{code/DS/ex7/main.cpp}
\textbf{链式栈的定义}\\
用单链表方式存储，指针的方向从栈顶向下链接。示意图如\ref{fig:ds_16}
\begin{figure}[!htb]\label{fig:ds_16}
    \centering
    \includegraphics[width=0.5\textwidth]{ds_16.png}
    \caption{链式栈示意图}
\end{figure}
\textbf{链式栈创建}
\begin{cpp}
    template <class T> class lnkStack <T>{
            private:                    // 栈的链式存储
            Link<T>* top;               // 指向栈顶的指针
            int size;                   // 存放元素的个数
            public:                     // 栈运算的链式实现
            lnkStack(int defSize) {     // 构造函数
                    top = NULL; size = 0;
                }
            ~lnkStack() {           //析构函数
                    clear();
                }
        }
\end{cpp}

压入栈顶

\begin{cpp}
    // 入栈操作的链式实现
    bool lnksStack<T>:: push(const T item) {
            Link<T>* tmp = new Link<T>(item, top);
            top = tmp;
            size++;
            return true;
        }
    Link(const T info, Link* nextValue){ // 具有两个参数的Link构造函数
            data = info;
            next = nextValue;
        }
\end{cpp}
从单链栈弹出元素
\begin{cpp}
    // 出栈操作的链式实现
    bool lnkStack<T>:: pop(T& item) {
            Link <T> *tmp;
            if (size == 0) {
                    cout << "栈为空,不能执行出栈操作"<< endl;
                    return false;
                }
            item = top->data;
            tmp = top->next;
            delete top;
            top = tmp;
            size--;
            return true;
        }
\end{cpp}
\textbf{顺序栈和链式栈的比较}
\begin{itemize}
    \item  时间效率
          \begin{itemize}
              \item 所有操作都只需常数时间
              \item 顺序栈和链式栈在时间效率上难分伯仲
          \end{itemize}
    \item 空间效率
          \begin{itemize}
              \item 顺序栈须说明一个固定的长度
              \item 链式栈的长度可变,但增加结构性开销
          \end{itemize}
\end{itemize}
实际应用中,顺序栈比链式栈用得更广泛：
\begin{itemize}
    \item  顺序栈容易根据栈顶位置,进行相对位移,快速定位并读取栈的内部元素
    \item – 顺序栈读取内部元素的时间为O(1),而链式栈则需要沿着指针链游走,显然慢些,读取第kk个元素需要时间为OO(kk)
\end{itemize}

\emph{ 一般来说,栈不允许“读取内部元素”,只能在栈顶操作。}

\textbf{栈的应用}\\
栈的特点:后进先出,体现了元素之间的透明性。\\
\textbf{常用来处理具有递归结构的数据}\\
\begin{itemize}
    \item 深度优先搜索
    \item 表达式求值
    \item 子程序/函数调用的管理
    \item 消除递归
\end{itemize}
\textbf{计算表达式的值}
\begin{itemize}
    \item 表达式的递归定义
          \begin{itemize}
              \item 基本符号集:{0,1,...,9,+,-,*,/,(,)}
              \item 语法成分集:{<表达式> , <项> , <因子> , <常数>, <数字> }
          \end{itemize}
    \item 中缀表达23+(34*45)/(5+6+7)式
    \item 后缀表达式23 34 45 * 5 6 + 7 + / +
\end{itemize}

\textbf{计算中缀表达式}
表达式：4 * x * (2 * x + a) – c
\begin{itemize}
    \item 运算符在中间
    \item 需要括号改变优先级
\end{itemize}
计算图如\ref{fig:ds_17}
\begin{figure}[!ht]\label{fig:ds_16}
    \centering
    \includegraphics[width=0.5\textwidth]{ds_17.png}
    \caption{中缀表达式计算}
\end{figure}
中缀表达式的语法公式：
\begin{Textcode}
    <表达式> ::= <项> + <项>
    | <项> - <项>
    | <项>
    <项> ::= <因子> * <因子>
    | <因子> / <因子>
    | <因子>
    <因子> ::= <常数>
    | ( <表达式> )
    <常数> ::= <数字>
    | <数字> <常数>
    <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
\end{Textcode}
表达式的递归图示\ref{fig:ds_16}
\begin{figure}[!ht]\label{fig:ds_16}
    \centering
    \includegraphics[width=0.5\textwidth]{ds_18.png}
    \caption{表达式的递归图示}
\end{figure}
后缀表达式\ref{fig:ds_19}：4 x * 2 x * a + * c –
\begin{itemize}
    \item 运算符在后面
    \item 完全不需要括号
\end{itemize}
\begin{figure}[!ht]\label{fig:ds_19}
    \centering
    \includegraphics[width=0.5\textwidth]{ds_19.png}
    \caption{后缀表达式示意图}
\end{figure}
后缀表达式
\begin{Textcode}
    <表达式>::=<项> <项> +
    | <项> <项> -
    | <项>
    <项>
    ::= <因子> <因子> *
    | <因子> <因子> /
    | <因子>
    <因子>::=<常数>
    <常数>::=<数字>
    | <数字> <常数>
    <数字>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
\end{Textcode}
后缀表达式求值

\begin{itemize}
    \item  循环:依次顺序读入表达式的符号序列(假设
          以=作为输入序列的结束),并根据读入的元
          素符号逐一分析
          \begin{enumerate}
              \item 当遇到的是一个操作数,则压入栈顶
              \item 当遇到的是一个运算符, 就从栈中两次取出栈顶,按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶
          \end{enumerate}
    \item 如此继续,直到遇到符号=,这时栈顶的值就
          是输入表达式的值
\end{itemize}
\textbf{后缀计算器的类定义}\\
\begin{cpp}
    class Calculator {
            private:
            Stack<double> s;            // 这个栈用于压入保存操作数
            // 从栈顶弹出两个操作数opd1和opd2
            bool GetTwoOperands(double& opd1,double& opd2);
            // 取两个操作数,并按op对两个操作数进行计算
            void Compute(char op);
            public:
            Calculator(void){};        // 创建计算器实例,开辟一个空栈
            void Run(void);            // 读入后缀表达式,遇“=”符号结束
            void Clear(void);          // 清除计算器,为下一次计算做准备
        };
    template <class ELEM>
    bool Calculator<ELEM>::GetTwoOperands(ELEM& opnd1, ELEM& opnd2) {
            if (S.IsEmpty()) {
                    cerr << "Missing operand!" <<endl;
                    return false;
                }
            opnd1 = S.Pop(); // 右操作数
            if (S.IsEmpty()) {
                    cerr << "Missing operand!" <<endl;
                    return false;
                }
            opnd2 = S.Pop(); // 左操作数
            return true;
        }
    template <class ELEM> void Calculator<ELEM>::Compute(char op) {
            bool result; ELEM operand1, operand2;
            result = GetTwoOperands(operand1, operand2);
            if (result == true)
            switch(op) {
                    case '+' : S.Push(operand2 + operand1); break;
                    case '-' : S.Push(operand2 - operand1); break;
                    case '*' : S.Push(operand2 * operand1); break;
                    case '/' : if (operand1 == 0.0) {
                            cerr << "Divide by 0!" << endl;
                            S.ClearStack();
                        } else S.Push(operand2 / operand1);
                    break;
                }
            else S.ClearStack();
        }
    template <class ELEM> void Calculator<ELEM>::Run(void) {
            char c; ELEM newoperand;
            while (cin >> c, c != '=') {
                    switch(c) {
                            case '+': case '-': case '*': case '/':
                            Compute(c);
                            break;
                            default:
                            cin.putback(c); cin >> newoperand;
                            S.Push(newoperand);
                            break;
                        }
                }
            if (!S.IsEmpty())
            cout << S.Pop() << endl; // 印出求值的最后结果
        }
\end{cpp}
\subsection{函数递归调用}
\begin{itemize}
    \item 阶乘
          \begin{equation*}
              f(n) =
              \begin{cases}
                  x\times f(n-1)\quad  n\geq 1 \\
                  1\quad n=1
              \end{cases}
          \end{equation*}

    \item 递归出口
          \begin{itemize}
              \item 递归终止的条件,即最小子问题的求解
              \item 可以允许多个出口
          \end{itemize}

    \item  递归规则(递归体+界函数)
          \begin{itemize}
              \item  将原问题划分成子问题
              \item  保证递归的规模向出口条件靠拢
          \end{itemize}
\end{itemize}
hanoi(n,X,Y,Z)
\begin{itemize}
    \item  移动n个环
    \item  X柱出发,将环移动到Z 柱
    \item  X、Y、Z都可以暂存(大盘不能压小盘)
\end{itemize}
河内塔示意图\ref{fig:ds_21}
\begin{figure}[!ht]\label{fig:ds_21}
    \centering
    \includegraphics[width=0.5\textwidth]{ds_21.png}
    \caption{河内塔示意图}
\end{figure}

\begin{cpp}
    void hanoi(int n, char X, char Y, char Z) {
            if (n <= 1)
            move(X,Z);
            else {                   // X上最大的不动,其他 n-1个环移到Y
                    hanoi(n-1,X,Z,Y);
                    move(X,Z);           // 移动最大环到Z,放好
                    hanoi(n-1,Y,X,Z);    // 把 Y上的n-1个环移到Z
                }
        }
    void move(char X, char Y)        // 把柱X的顶部环移到柱Y
    {
    cout << "move" << X << "to" << Y << endl;
    }
\end{cpp}
递归调转示意图\ref{fig:ds_19}
\begin{figure}[!ht]\label{fig:ds_19}
    \centering
    \includegraphics[width=0.5\textwidth]{ds_19.png}
    \caption{递归转非递归}
\end{figure}
递归运行时，堆栈的进退以及通过堆栈传递参数
\begin{figure}[!ht]\label{fig:ds_20}
    \centering
    \includegraphics[width=0.5\textwidth]{ds_20.png}
    \caption{递归运行}
\end{figure}
\begin{equation*}
    \begin{cases}
        n+1\quad n<2 \quad \\
        f(n/2)*f(n/4) \quad n\geq 2
    \end{cases}
\end{equation*}
\begin{cpp}
    void exmp(int n,int & f)
    {
            int u1, u2;
            if (n<2)
            f = n+1;
            else {
                    exmp((int)(n/2), u1);
                    exmp((int)(n/4), u2);
                    f = u1*u2;
                }
        }
\end{cpp}
\subsection{队列}
队列是一个简单的等待序列，在尾部加入元素时队列加长，在前端删除数据时队列缩短。和栈不同，队列是一种使用两端的结构：一端用来加入新元素，另一端用来删除元素。因此最后一个元素必须等到排在它之前的所有元素都删除后才能操作。队列是一种先进先出（FIFO）的结构。下面使用一维数组实现循环数组。循环数组作为一种数据结构只是在代码层面对这种结构做限制。如图\ref{fig:queue_circle}.判断循环队列有两种方式：
\begin{enumerate}\label{en:isfull}
    \item 第一个元素在第一个单元。最后一个元素在最后一个单元（a）。
    \item 第一个元素和最后一个元素相邻并在其右面。
\end{enumerate}
enqueue()可以看成循环数组上的操作(c)，但实际上这时在一维数组上操作。因此，如果最后一个元素在最后一个单元中，而且数组的开始单元为空，则将新元素放在开始单元（d）。如果最后一个元素在其它位置，且空间允许的话，新的元素就放到它的后面（e）。

循环队列结构：
\begin{figure}[H]\label{fig:queue_circle}
    \centering
    \includegraphics[width=\textwidth]{queue_circle.png}
    \caption{循环队列}
\end{figure}
\cppfile{code/DS/ex8/array_queue.hpp}
测试代码:
\cppfile{code/DS/ex8/main.cpp}
\cppfile[firstline=49,lastline=52]{code/DS/ex8/array_queue.hpp}
上面代码测试循环队列是否已满,如\ref{en:isfull}。
enqueue的时候有两种情况一种是（d）对应的最后一个元素在数组最后面，这个时候需要将一维数组的第一个元素作为环形队列的最后一个元素添加，last指向一维数组的第一个元素如果环形队列为空，则第一个元素指向一维数组的0位置。
\cppfile[firstline=23,lastline=29]{code/DS/ex8/array_queue.hpp}
出队包含三种情况：
\begin{enumerate}
    \item 第一个元素和最后一个元素指针指向同一个元素（指空）。
    \item first指向last-1，因为是环形队列，下一个元素就是first=0。
    \item first指针后移动一位。
\end{enumerate}
\subsection{优先队列}
在优先队列中，根据元素的优先级以及在队列中的当前位置决定出队列的顺序。在STL中实现了优先队列priority\_queue，priority\_queue容器默认使用deque容器总是把邮件即最高的元素放在队列的最前方以维持队列的顺序。为此插入push操作使用两个参数的的bool函数，将对列中的元素重新排序以满足这个要求，该函数可以使用<运算符，元素的值越大优先级越高。如果元素值越小优先级越高则需要使用函数greater表明在决定邮件队列中插入新元素push()应该应用运算符>而不是<。
优先队列的例子：
\cppfile{code/DS/ex9/main.cpp}
对类Person中年龄最大的输出。
\cppfile{code/DS/ex10//main.cpp}
\section{树}
二叉树节点的ADT
\begin{cpp}
    templace<class T>
    class BinaryTreeNode{
            friend class BinaryTree<T>;
            private:
            T info;
            public:
            BinaryTreeNode();
            BinaryTreeNode(const T &ele);
            BinaryTreeNode(const T & ele,BinaryTreeNode<T> *l,BinaryTreeNode<T> *r);
            T value() const;
            BinaryTreeNode<T>* leftchild() const;
            BinaryTreeNode<T>* rightchild() const;
            void setLeftchild(BinaryTreeNode<T> *);
            void setRightchild(BinaryTreeNode<T>*);
            void isLeaf() const;
            BinaryTreeNode<T>& operator = (const BinaryTreeNode<T>&Node);
        };
\end{cpp}
二叉树的ADT
\begin{cpp}
    templace <class T>
    class BinaryTree{
            private:
            BinaryTreeNode<T>* root;
            public:
            BinaryTreeNode(){root = NULL;}
            ~BinaryTreeNode(){DeleteBinaryTree(root);}
            bool isEmpty() const;
            BinaryTreeNode<T>* Root(){return root;}
            BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *current);
            // 返回父
            BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T> *current);// 左兄
            BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T> *current); // 右兄
            void CreateTree(const T& info,
            BinaryTree<T>& leftTree, BinaryTree<T>& rightTree); // 构造新树
            void PreOrder(BinaryTreeNode<T> *root); // 前序遍历二叉树或其子树
            void InOrder(BinaryTreeNode<T> *root);
            // 中序遍历二叉树或其子树
            void PostOrder(BinaryTreeNode<T> *root); // 后序遍历二叉树或其子树
            void LevelOrder(BinaryTreeNode<T> *root); // 按层次遍历二叉树或其子树
            void DeleteBinaryTree(BinaryTreeNode<T> *root); // 删除二叉树或其子树
        };
\end{cpp}
遍历二叉树：
\begin{itemize}
    \item 系统地访问数据结构中的节点
    \item 每个节点都正好被访问一次
\end{itemize}
\begin{itemize}
    \item 先序遍历：访问根节点，左子树，右子树
    \item 中序遍历：访问左子树 ，根节点，右子树
    \item 后序遍历：左子树，右子树，根节点
\end{itemize}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree1.png}
    \caption{树的遍历}
\end{figure}
\begin{itemize}
    \item 先序遍历：A B D E G C F H I
    \item 中序遍历：D B G E A C H F I
    \item 后序遍历：D G E B H I F C A
\end{itemize}
表达式二叉树
\begin{itemize}
    \item - + * a b c * a + b c
    \item a * b + c - a * b + c
    \item a b * c + a b c + * -
\end{itemize}
深度优先遍历二叉树
\begin{cpp}
    template<class T>
    void BinaryTree<T>::DepthOrder(BinaryTreeNode<T>* root)
    {
            if(root!=NULL)
            {
                    Visit(root);
                    DepthOrder(root->leftchild())://先序遍历
                    Visit(root);//中序遍历
                    DepathOrder(root->rightcgild());//递归访问右子树
                    Visit(root);//后序遍历
                }
        }
\end{cpp}
非递归先序遍历二叉树：
\begin{itemize}
    \item  遇到一个结点,就访问该结点,并把此结点的非空右结点推入栈中,然后下降去遍历它的左子树;
    \item 遍历完左子树后,从栈顶托出一个结点,并按照它的右链接指示的地址再去遍历该结点的右子树结构。
\end{itemize}
\begin{cpp}
    template<class T> void
    BinaryTree<T>::PreOrderWithoutRecusion
    (BinaryTreeNode<T>* root) {
            using std::stack;  // 使用STL中的stack
            stack<BinaryTreeNode<T>* > aStack;
            BinaryTreeNode<T>* pointer=root;
            aStack.push(NULL);  // 栈底监视哨
            while(pointer) {  // 或者!aStack.empty()
                    Visit(pointer->value());  // 访问当前结点
                    if (pointer->rightchild() != NULL) // 右孩子入栈
                    aStack.push(pointer->rightchild());
                    if (pointer->leftchild() != NULL)
                    pointer = pointer->leftchild(); //左路下降
                    else {  // 左子树访问完毕,转向访问右子树
                            pointer = aStack.top();
                            aStack.pop();  // 栈顶元素退栈
                        }

                }
        }
\end{cpp}
非递归中序遍历二叉树
\begin{itemize}
    \item  遇到一个结点
          \begin{itemize}
              \item 把它推入栈中
              \item 遍历其左子树
          \end{itemize}
    \item 遍历完左子树
          \begin{itemize}
              \item 从栈顶托出该结点并访问之
              \item 按照其右链地址遍历该结点的右子树
          \end{itemize}
\end{itemize}
\begin{cpp}
    template<class T> void
    BinaryTree<T>::InOrderWithoutRecusion(BinaryTreeNode<T>* root)
    {
            using std::stack;
            stack<BinaryTreeNode<T>* > aStack;
            BinaryTreeNode<T>* pointer = root;
            while (!aStack.empty() || pointer) {
                    if (pointer ) {
                            // Visit(pointer->value()); 前序访问点
                            aStack.push(pointer);  // 当前结点地址入栈
                            // 当前链接结构指向左孩子
                            pointer = pointer->leftchild();
                        } //end if
                    else {        //左子树访问完毕,转向访问右子树
                            pointer = aStack.top();
                            aStack.pop();  //栈顶元素退栈
                            Visit(pointer->value());  //访问当前结点
                            //当前链接结构指向右孩子
                            pointer=pointer->rightchild();
                        } //end else
                } //end while
        }
\end{cpp}
非递归后序遍历二叉树
\begin{itemize}
    \item 给栈中元素加上一个特征位
          \begin{itemize}
              \item Left表示已进入该节点的左子树，将从左边回来
              \item Right 表示已进入该节点的右子树，将从右边回来
          \end{itemize}
\end{itemize}
\begin{cpp}
    enum Tags{Left,Right};  // 定义枚举类型标志位
    template <class T>
    class StackElement {// 栈元素的定义
            public:
            BinaryTreeNode<T>* pointer;  //指向二叉树结点的指针
            Tags tag;  // 标志位
        };
    template<class T>
    void BinaryTree<T>::PostOrderWithoutRecursion(BinaryTreeNode<T>* root) {
            using std::stack;  // 使用STL的栈
            StackElement<T> element;
            stack<StackElement<T > > aStack;
            BinaryTreeNode<T>* pointer;
            pointer = root;
            while (!aStack.empty() || pointer) {
                    while (pointer != NULL) {  // 沿非空指针压栈,并左路下降
                            element.pointer = pointer;
                            element.tag = Left;
                            aStack.push(element);  // 把标志位为Left的结点压入栈
                            pointer = pointer->leftchild();
                        }
                    element = aStack.top(); aStack.pop(); // 获得栈顶元素,并退栈
                    pointer = element.pointer;
                    if (element.tag == Left) { // 如果从左子树回来
                            element.tag = Right;
                            aStack.push(element); // 置标志位为Right
                            pointer = pointer->rightchild();
                        }
                    else {  // 如果从右子树回来
                            Visit(pointer->value());  // 访问当前结点
                            pointer = NULL;  // 置point指针为空,以继续弹栈
                        }
                }
        }
\end{cpp}
各种遍历算法的时间代价分析：
\begin{itemize}
    \item 在各种遍历中，每个节点都被访问且只被访问一次，时间代价为O(n)。
    \item 非递归保存出入栈（或者队列）时间
          \begin{itemize}
              \item 先序，中序，某些节点出入栈一次，不超过O(n)。
              \item 后续，每个节点分别从左，右边各入出一次，O(n)。
          \end{itemize}
\end{itemize}
深搜：栈的深度和树的高度有关，最好O(logn),最坏O(n)。
\subsection{二叉树的概念}
二叉树 (binary tree) 由结点的有限
集合构成
\begin{definition}[二叉树]
    二叉树由节点的有限集合构成，这个有限集合或者为空集 (empty)或者为由一个根结点 (root) 及两棵互不相交、分别称作这个根的左子
    树 (left subtree) 和右子树 (rightsubtree) 的二叉树组成的集合
\end{definition}
二叉树可以是空集合,因此根可以有空的左子树或右子树,或者左右子树皆为空。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree3.png}
    \caption{树}
\end{figure}
\begin{definition}[节点]
    \begin{itemize}
        \item 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
        \item 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
        \item 兄弟节点：具有相同父节点的节点互称为兄弟节点。
        \item 没有子树的节点称为叶子节点。
        \item 非终端节点称为分支节点。
    \end{itemize}
\end{definition}

\begin{definition}[边]
    两个节点的有序对称为边。
\end{definition}
\begin{definition}[路径]
    除了根节点$k_0$外的任何节点$k\in K$都存在一个节点序列$k_0,k_1,\cdots,k_s$使得$k_0$就是树根，且$k_s = k$，其中有序对$<k_{i-1},k_i>\in r(1\leq i\leq s)$这样的节点序列称为从根到节点k的一条路径，路径长度为s（包含的边数）
\end{definition}
\begin{definition}[祖先，后代]
    若有一条由k到达$k_s$的路径，则称k为$k_s$的祖先，$k_s$是k的子孙。
\end{definition}
\begin{definition}[层数]
    根为第0层，其它节点的层数等于其父节点的层数加上1。
\end{definition}
\begin{definition}[深度]
    层数最大的叶节点的层数。
\end{definition}
\begin{definition}[高度]
    层数最大的叶子节点的程序加上1。
\end{definition}
\begin{definition}[满二叉树]
    如果一棵二叉树的 任何 结点,或者是树叶,或者恰有两棵非空子树,则
    此二叉树称作 满二叉树
\end{definition}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree4.png}
    \caption{满二叉树}
\end{figure}
\begin{definition}[完全二叉树]
    最多只有最下面的两层结点度数可以小于2，最下一层的结点都集中最左边。
\end{definition}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree5.png}
    \caption{完全二叉树}
\end{figure}
\begin{definition}[扩充二叉树]
    所有空子树,都增加空树叶， 外部路径长度E和内部路径长度I， 满足:E=I+2n(n是内部结点个数)。
\end{definition}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree6.png}
    \caption{扩充二叉树}
\end{figure}
\begin{itemize}
    \item [性质1] 在二叉树中,第i层上最多有 $2^i$个结点($i\geq 0$)
    \item [性质2] 深度为 k 的二叉树至多有$2^{k+1}-1$个结点($k\geq$)，其中深度(depth)定义为二叉树中层数最大的叶结点的层数
    \item [性质3] 一棵二叉树,若其终端结点数为 $n_0$ ,度为2的结点数为 $n_2$ ,则 $n_0 =n_2 +1$
    \item [性质4] 满二叉树定理:非空满二叉树树叶数目等于其分支结点数加1
    \item [性质5] 满二叉树定理推论:一个非空二叉树的空子树数目等于其结点数加1
    \item [性质6] 有n个结点(n>0)的完全二叉树的高度为 $\lfloor\log_2 (n+1)\rfloor$ (深度为$\lfloor\log_2(n+1) \rfloor -1$)
\end{itemize}
\subsection{宽度优先遍历二叉树}
从二叉树的第 0 层(根结点)开始,自上至下 逐层遍历;在同一层中,按照 从左到右 的顺序对结点逐一访问。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree7.png}
    \caption{宽度优先遍历}
\end{figure}
遍历结果为：A B C D E F G H I。
\begin{cpp}
    void BinaryTree<T>::LevelOrder(BinaryTreeNode<T>* root){
            using std::queue;  // 使用STL的队列
            queue<BinaryTreeNode<T>*> aQueue;
            BinaryTreeNode<T>* pointer = root; // 保存输入参数
            if (pointer) aQueue.push(pointer); // 根结点入队列
            while (!aQueue.empty()) {  // 队列非空
                    pointer = aQueue.front();  // 取队列首结点
                    aQueue.pop();  // 当前结点出队列
                    Visit(pointer->value());  // 访问当前结点
                    if(pointer->leftchild())
                    aQueue.push(pointer->leftchild()); // 左子树进队列
                    if(pointer->rightchild())
                    aQueue.push(pointer->rightchild());// 右子树进队列

                }
        }
\end{cpp}
在各种遍历中,每个结点都被访问且只被访问一次,时间代价为O(n)非递归保存入出栈(或队列)时间,宽搜,正好每个结点入/出队一次,O(n)
宽度优先搜索：与数的最大宽度有关，最好Q（1）最坏Q(n)。

\textbf{二叉树的链式存储结构}\\*
二叉链表：指针left和right分别指向节点的左孩子和右孩子。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree8.png}
    \caption{二叉链表}
\end{figure}
三叉链表：指针left和right，分别指向节点的左孩子和右孩子，增加一个父指针
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree9.png}
    \caption{三叉链表}
\end{figure}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree10.png}
    \caption{二叉链表表示的树}
\end{figure}
指向父母的指针parent。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree11.png}
    \caption{三叉链表表示的树}
\end{figure}
在BinaryTreeNode类中添加两个私有数据成员
\begin{cpp}
    private:
    BinaryTreeNode<T> *left;  // 指向左子树的指针
    BinaryTreeNode<T> *right; // 指向右子树的指针
    template <class T> class BinaryTreeNode {
            friend class BinaryTree<T>;  // 声明二叉树类为友元类
            private:
            T info;  // 二叉树结点数据域
            public:
            BinaryTreeNode(); // 缺省构造函数
            BinaryTreeNode(const T& ele);  // 给定数据的构造
            BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l,
            BinaryTreeNode<T> *r); // 子树构造结点
        }
\end{cpp}
递归框架寻找父节点：
\begin{cpp}
    template<class T>
    BinaryTreeNode<T>* BinaryTree<T>::
    Parent(BinaryTreeNode<T> *rt, BinaryTreeNode<T> *current) {
            BinaryTreeNode<T> *tmp,
            if (rt == NULL) return(NULL);
            if (current == rt ->leftchild() || current == rt->rightchild())
            return rt; // 如果孩子是current则返回parent
            if ((tmp =Parent(rt- >leftchild(), current) != NULL)
            return tmp;
            if ((tmp =Parent(rt- > rightchild(), current) != NULL)
            return tmp;
            return NULL;
        }
\end{cpp}
非递归框架找父节点：
\begin{cpp}
    BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *current) {
            using std::stack;  // 使用STL中的栈
            stack<BinaryTreeNode<T>* > aStack;
            BinaryTreeNode<T> *pointer = root;
            aStack.push(NULL);  // 栈底监视哨
            while (pointer) {  // 或者!aStack.empty()
                    if (current == pointer->leftchild() || current == pointer->rightchild())
                    return pointer;  // 如果pointer的孩子是current则返回parent
                    if (pointer->rightchild() != NULL)  // 非空右孩子入栈
                    aStack.push(pointer->rightchild());
                    if (pointer->leftchild() != NULL)
                    pointer = pointer->leftchild();  // 左路下降
                    else {    // 左子树访问完毕,转向访问右子树
                            pointer=aStack.top(); aStack.pop(); // 获得栈顶元素,并退栈
                        } } }
\end{cpp}
空间开销分析：
\begin{itemize}
    \item 存储密度$\alpha(\leq 1)$比啊是数据结构存储的效率。\[\alpha(\text{存储密度}=\frac{\text{数据本身存储量}}{\text{整个结构占用的存储总量}})\]
    \item 结构性开销$\gamma=1-\alpha$
\end{itemize}
\textbf{空间开销}
根据满二叉树订立：一般的指针是空的。每个节点存两个指针，一个数据域：
\begin{itemize}
    \item 总空间（2p+d）n
    \item 结构性开销:2pn
    \item 如果p = d,则结构性开销2p(2p+d) = 2/3
\end{itemize}
C++ 可以用两种方法来实现不同的分支与叶结点:
\begin{itemize}
    \item  用union联合类型定义
    \item  使用C++的子类来分别实现分支结点与叶结点,并采用虚函数isLeaf来区别分支结点与叶结点
\end{itemize}
早期节省内存资源
\begin{itemize}
    \item  利用结点指针的一个空闲位(一个bit)来标记结点所属的类型
    \item 利用指向叶的指针或者叶中的指针域来存储该叶结点的值
\end{itemize}
\textbf{顺序方法存储二叉树}\\*
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree12.png}
    \caption{二叉树的顺序存储}
\end{figure}
\begin{itemize}
    \item 把节点按一定的顺序存储到一片连续的存储单元。
    \item 使节点在序列中的位置反映出相应的结构信息。
\end{itemize}
存储结构上是线性的，逻辑结构上它让然是二叉树形结构。
从节点的编号就可以推知其父母，孩子，兄弟的编号
\begin{itemize}
    \item  当 2i+1<n 时,结点 i 的左孩子是结点 2i+1,否则结点i没有左孩子
    \item 当 2i+2<n 时,结点 i 的右孩子是结点 2i+2,否则结点i没有右孩子
\end{itemize}
完全二叉树的下标公式：
\begin{itemize}
    \item 当 0<i<n 时,结点 i 的父亲是结点 $\lfloor(i-1)\rfloor$
    \item 当 i 为偶数且 0<i<n 时,结点 i 的左兄弟是结点 i-1，否则结点 i 没有左兄弟。
    \item 当 i 为奇数且 i+1<n 时,结点i的右兄弟是结点 i+1,否则结点i没有右兄弟。
\end{itemize}
\textbf{二叉搜索树}\\*
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree13.png}
    \caption{二叉搜索树}
\end{figure}
\begin{definition}[二叉搜索树（Binary Search Tree(BST)）]
    或者是一棵空树或者是具有如下性质的二叉树：
    \begin{itemize}
        \item 对于任何一个节点，设其值为K则：该节点的左子树（若不空）的任意一个节点的值都小于K。该节点的右子树（若不空）的任意一个节点的值都大于K，而且他的左右子树也分别是BST。
    \end{itemize}
\end{definition}
性质：中序遍历是正序的（由小到大排列）。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree14.png}
    \caption{二叉树的删除}
\end{figure}
\begin{cpp}
    void BinarySearchTree<T>:::removehelp(BinaryTreeNode <T> *& rt, const T val) {
            if (rt==NULL) cout<<val<<" is not in the tree.\n";
            else if (val < rt->value())
            removehelp(rt->leftchild(), val);
            else if (val > rt->value())
            removehelp(rt->rightchild(), val);
            else {    // 真正的删除
                    BinaryTreeNode <T> * temp = rt;
                    if (rt->leftchild() == NULL) rt = rt->rightchild();
                    else if (rt->rightchild() == NULL) rt = rt->leftchild();
                    else {
                            temp = deletemin(rt->rightchild());
                            rt->setValue(temp->value());
                        }
                    delete temp;
                }
        }
\end{cpp}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree5.png}
    \caption{删除右子树最小节点}
\end{figure}
找右子树中最小节点，并删除。
\begin{cpp}
    template <class T>
    BinaryTreeNode* BST::deletemin(BinaryTreeNode <T> *& rt) {
            if (rt->leftchild() != NULL)
            return deletemin(rt->leftchild());
            else { // 找到右子树中最小,删除
                    BinaryTreeNode <T> *temp = rt;
                    rt = rt->rightchild();
                    return temp;
                }
        }
\end{cpp}
二叉搜索树是适用于内存储器的一种重要的树形索引，常用红黑树、伸展树等,以维持平衡外存常用B/B+树。
\subsubsection{堆的定义和实现}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree16.png}
    \caption{堆的实现}
\end{figure}
\begin{definition}[最小堆]
    $K_0,K_1,\cdots,K_{n-1}$具有如下特性：
    \begin{itemize}
        \item $K_i\leq K_{2i+1}(i=0,1,\ldots,\lfloor n/2\rfloor-1)$
        \item $K\leq K_{2i+2}$
    \end{itemize}
\end{definition}
堆的性质：
\begin{itemize}
    \item 完全二叉树的层次序列，可以使用数组表示。
    \item 堆中存储的数据是局部有序的，堆部位以。节点的值和其孩子的值之间存在限制。任何一个节点和其兄弟之间都没有直接的限制。
    \item 从逻辑的角度看，堆实际上是一种树形结构。
\end{itemize}
\begin{cpp}
    template <class T>
    class MinHeap {  // 最小堆ADT定义
            private:
            T* heapArray;  // 存放堆数据的数组
            int CurrentSize; // 当前堆中元素数目
            int MaxSize;  // 堆所能容纳的最大元素数目
            void BuildHeap();  // 建堆
            public:
            MinHeap(const int n);  // 构造函数,n为最大元素数目
            virtual ~MinHeap(){delete []heapArray;};  // 析构函数
            bool isLeaf(int pos) const;  // 如果是叶结点,返回TRUE
            int leftchild(int pos) const;  // 返回左孩子位置
            int rightchild(int pos) const;  // 返回右孩子位置
            int parent(int pos) const;  // 返回父结点位置
            bool Remove(int pos, T& node);   // 删除给定下标的元素
            bool Insert(const T& newNode);  // 向堆中插入新元素newNode
            T& RemoveMin();  // 从堆顶删除最小值
            void SiftUp(int position);  // 从position向上开始调整,使序列成为堆
            void SiftDown(int left);  // 筛选法函数,参数left表示开始处理的数组下标
        }
\end{cpp}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{tree17.png}
    \caption{对最小堆用筛选法}
\end{figure}
\begin{cpp}
    template <class T>
    void MinHeap<T>::SiftDown(int position) {
            int i = position;  // 标识父结点
            int j = 2*i+1;  // 标识关键值较小的子结点
            Ttemp = heapArray[i]; // 保存父结点
            while (j < CurrentSize) {
                    if((j < CurrentSize-1)&&
                    (heapArray[j] > heapArray[j+1]))
                    j++;  // j指向数值较小的子结点
                    if (temp > heapArray[j]) {
                            heapArray[i] = heapArray[j];
                            i = j;
                            j = 2*j + 1;    // 向下继续
                        }
                    else break;
                }
            heapArray[i]=temp;
        }
\end{cpp}

对最小堆用shiftup向上调整：
\begin{cpp}
    template<class T>
    void MinHeap<T>::SiftUp(int position) {
    // 从position向上开始调整,使序列成为堆
    int temppos=position;
    // 不是父子结点直接swap
    T temp=heapArray[temppos];
    while((temppos>0) && (heapArray[parent(temppos)] > temp)) {
    heapArray[temppos]=heapArray[parent(temppos)];
    temppos=parent(temppos);
    }
    heapArray[temppos]=temp;// 找到最终位置
    }
\end{cpp}
建最小堆的过程：
首先,将 n 个关键码放到一维数组中
\begin{itemize}
    \item  整体不是最小堆
    \item 所有叶结点子树本身是堆 当 $i \geq\lfloor n/2 \rfloor$时,以关键码 K i 为根的子树已经是堆。
    \item 从倒数第二层,$i=\lfloor n/2 \rfloor$-1开始从右至左依次调整
    \item  直到整个过程到达树根,整棵完全二叉树就成为一个堆。
\end{itemize}
建最小堆：从第一个分支结点 heapArray[CurrentSize/2-1]开始,自底向上逐步把以子树调整成堆。
\begin{cpp}
    template<class T>
    void MinHeap<T>::BuildHeap()
    {
            // 反复调用筛选函数
            for (int i=CurrentSize/2-1; i>=0; i--)
            SiftDown(i);
        }
\end{cpp}
最小堆插入新元素：
\begin{cpp}
    template <class T>
    bool MinHeap<T>::Insert(const T& newNode)
    //向堆中插入新元素newNode
    {
    if(CurrentSize==MaxSize)  // 堆空间已经满
    return false;
    heapArray[CurrentSize]=newNode;
    SiftUp(CurrentSize);  // 向上调整
    CurrentSize++;
    }
\end{cpp}
最小堆删除元素操作
\begin{cpp}
    template<class T>
    bool MinHeap<T>::Remove(int pos, T& node) {
    if((pos<0)||(pos>=CurrentSize))
    return false;
    T temp=heapArray[pos];
    heapArray[pos]=heapArray[--CurrentSize];
    if (heapArray[parent(pos)]> heapArray[pos])
    SiftUp(pos);    //上升筛
    else SiftDown(pos); // 向下筛
    node=temp;
    return true;
    }
\end{cpp}
堆的效率分析：\\*
n 个结点的堆,高度 $d = \lfloor log 2 n + 1\rfloor$ 。根为第 0 层,则第 i 层结点个数为 $2^i$,
考虑一个元素在堆中向下移动的距离 。
\begin{itemize}
    \item 大约一半的结点深度为 d-1,不移动(叶)。
    \item 四分之一的结点深度为 d-2,而它们至多能向下移动一层。
    \item 树中每向上一层,结点的数目为前一层的一半,而子树高度加一。因而元素移动的最大距离的总数为$\sum_{i=1}^{\log n}(i-1)\frac{n}{2^i}=O(n)$
\end{itemize}
最小堆操作效率：\\*
建堆算法时间代价为O(n)，堆有log n层深，插入节点，删除普通元素和删除最小元素的平均时间代价和最差时间代价都是O(log n)

堆可以用于实现优先队列
\begin{itemize}
    \item 优先队列，1.根据需要释放具有最小(大)值的对象。2. 最大树、 左高树HBLT、WBLT、MaxWBLT
    \item 改变已存储于优先队列中对象的优先权。 辅助数据结构帮助找到对象
\end{itemize}
\textbf{树的存储实现}
\cppfile{code/DS/tree/ex2/Tree.h}
\cppfile{code/DS/tree/ex2/Tree.cpp}
\cppfile{code/DS/tree/ex2/main.cpp}
\textbf{数的链表实现}

节点的头文件定义
\cppfile{code/DS/tree/ex3/Node.hpp}
节点的实现
\cppfile{code/DS/tree/ex3/Node.cc}
树的头文件定义：
\cppfile{code/DS/tree/ex3/Tree.hpp}
树的实现：
\cppfile{code/DS/tree/ex3/Tree.cc}
验证代码：
\cppfile{code/DS/tree/ex3/main.cpp}
\subsection{Haffman编码}
霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。

霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
霍夫曼编码的具体步骤如下：
\begin{itemize}
    \item 将信源符号的概率按减小的顺序排队。
    \item 把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率１。
    \item 画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。
    \item 将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
\end{itemize}
\begin{example}[计算haffuman编码]
    现有一个由5个不同符号组成的30个符号的字符串：BABACAC ADADABB CBABEBE DDABEEEBB。
    \begin{table}[H]
        \centering
        \begin{tabular}{ll}
            \toprule
            字符 & 次数 \\
            \midrule
            A    & 8    \\
            B    & 10   \\
            C    & 3    \\
            D    & 4    \\
            E    & 5    \\
            \bottomrule
        \end{tabular}
        \caption{计算字符出现的次数}
    \end{table}
    \begin{enumerate}
        \item 将出现次数最小的两个数3和4相加组合成7。
              \begin{figure}[H]
                  \centering
                  \includegraphics[width=0.5\textwidth]{haffman_1.pdf}
                  \caption{第一步}
              \end{figure}
        \item 第二步：将最低值5和7组合成12。
              \begin{figure}[H]
                  \centering
                  \includegraphics[width=0.5\textwidth]{haffman_2.pdf}
                  \caption{第二步}
              \end{figure}
        \item 第三步：将8，10相加组合成18。
              \begin{figure}[H]
                  \centering
                  \includegraphics[width=0.5\textwidth]{haffman_3.pdf}
                  \caption{第三步}
              \end{figure}
        \item 第四步：最低值12和18相加，结束。
              \begin{figure}[H]
                  \centering
                  \includegraphics[width=0.5\textwidth]{haffman_4.pdf}
                  \caption{第四步}
              \end{figure}
    \end{enumerate}
    沿着二叉树顶部到每个字符路径获得每个符号的编码。
    \begin{table}[H]
        \centering
        \begin{tabular}{lll}
            \toprule
            字符 & 次数 & 编码 \\
            \midrule
            A    & 8    & 10   \\
            B    & 10   & 11   \\
            C    & 3    & 010  \\
            D    & 4    & 011  \\
            E    & 5    & 00   \\
            \bottomrule
        \end{tabular}
    \end{table}
    我们可以看到出现次数（概率）越多的会越在上层，编码也越短，出现频率越少的就越在下层，编码也越长。当我们编码的时候，我们是按“bit”来编码的，解码也是通过bit来完成，如果我们有这样的bitset “10111101100” 那么其解码后就是 “ABBDE”。所以，我们需要通过这个二叉树建立我们Huffman编码和解码的字典表。

    这里需要注意的是，Huffman编码使得每一个字符的编码都与另一个字符编码的前一部分不同，不会出现像‘A’：00，  ‘B’：001，这样的情况，解码也不会出现冲突。
\end{example}
\begin{remark}
    利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限；输入符号数受限于可实现的码表尺寸；译码复杂；需要实现知道输入符号集的概率分布；没有错误保护功能。
\end{remark}
\section{多叉树}
平衡多分数(Balanced Tree)
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{btree.png}
    \caption{BTree示意图}
    \begin{definition}[m阶B树]
        \begin{enumerate}
            \item 每个节点至多有m个子节点。
            \item 除根节点和叶子节点外，其它每个节点至少有$\frac{m}{2}$个子节点。
            \item 根节点至少有两个子节点。，为一里外的是根节点就是叶节点的时候没有子节点，此时B数只包含一个节点。
            \item 所有叶节点在统一层。
            \item 所有k个子节点的非根节点恰好包含k-1个关键码。
        \end{enumerate}
    \end{definition}
\end{figure}
\textbf{b数的性质}
\begin{enumerate}
    \item 数高平衡，所有叶子节点都在统一层。
    \item 关键码没有重复，父节点中的关键码是其子节点的分界。
    \item B树把（值接近）相关记录放在同一个磁盘页中，从而利用访问局部性原理。
    \item B树保证树中至少有一定比例的节点是满的。这样能够改进空间里用率，减少检索和更新操作的磁盘读取数目。
\end{enumerate}
B数的节点结构：B数的一个包含j个关键码，j+1个指针的几点的一般形式为：
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{btree_struct.png}
    \caption{b树的结点结构}
\end{figure}

\section{数据结构与算法}
\subsection{双端队列}
队列是一种先入先出的数据结构，\figref{fig:common_queue}对于给定长度的队列如果指定元素到达队列末尾，通常认为队列已满，即使弹出元素后此队列有多余空间。为此我们可以使用循环队列解决此问题。
\begin{figure}[!htbp]
    \centering
    \includegraphics*[width=0.8\textwidth]{queue}
    \caption{普通队列浪费存储空间}
    \label{fig:common_queue}
\end{figure}
\figref{fig:dequeue}双端队列可以解决存储空间的问题：
\begin{figure}[!htbp]
    \centering
    \includegraphics*[width=\textwidth]{dequeue}
    \caption{双端队列}
    \label{fig:dequeue}
\end{figure}
双端队列需要实现的方法：
\begin{itemize}
    \item[isEmpty] 判断队列是否为空。
    \item[isFull] 判断队列是否已满。
    \item[enQueue] 入队。
    \item[deQueue] 出队。
    \item[Front] 获取队列最前面的元素。
    \item[Rear] 获取队列尾部元素。
\end{itemize}
为此需要成员变量：
\begin{itemize}
    \item head：指向双端队列队首元素。
    \item tai：指向双端队列队尾元素。
    \item size：队列长度。
    \item count：队列中元素个数。
\end{itemize}
队列头文件如下：
\cppfile{code/DS/MyCircularQueue/include/MyCircularQueue.h}
函数实现：
\cppfile{code/DS/MyCircularQueue/src/MyCircularQueue.cpp}
\subsection{队列的应用}
\begin{itemize}
    \item BFS遍历
\end{itemize}
队列实现的BFS模版：
\begin{cpp}
    int BFS(Node root, Node target) {
            Queue<Node> queue;  // store all nodes which are waiting to be processed
            int step = 0;       // number of steps neeeded from root to current node
            // 添加元素入队列操作，出队需要判断队列是否为空
            add root to queue;
            // BFS
            while (queue is not empty) {
                    step = step + 1;
                    // 遍历队列中的每个元素，将每个元素的邻接点加入队列
                    int size = queue.size();
                    for (int i = 0; i < size; ++i) {
                            Node cur = the first node in queue;
                            return step if cur is target;
                            for (Node next : the neighbors of cur) {
                                    add next to queue;
                                }
                            remove the first node from queue;
                        }
                }
            return -1;          // there is no path from root to target
        }
\end{cpp}
\begin{enumerate}
    \item
\end{enumerate}
有时，确保我们永远不会访问一个结点两次很重要。否则，我们可能陷入无限循环。如果是这样，我们可以在上面的代码中添加一个哈希集来解决这个问题。这是修改后的伪代码：
\begin{cpp}
    int BFS(Node root, Node target) {
            Queue<Node> queue;  // store all nodes which are waiting to be processed
            Set<Node> used;     // store all the used nodes
            int step = 0;       // number of steps neeeded from root to current node
            // initialize
            add root to queue;
            add root to used;
            // BFS
            while (queue is not empty) {
                    step = step + 1;
                    // iterate the nodes which are already in the queue
                    int size = queue.size();
                    for (int i = 0; i < size; ++i) {
                            Node cur = the first node in queue;
                            return step if cur is target;
                            for (Node next : the neighbors of cur) {
                                    // 加入节点是否访问过的判断。
                                    if (next is not in used) {
                                            add next to queue;
                                            add next to used;
                                        }
                                }
                            remove the first node from queue;
                        }
                }
            return -1;          // there is no path from root to target
        }
\end{cpp}
通常在二叉树的遍历中不需要使用hash结构，因为在此结构中不存在一个叶子节点同时属于两个节点。
\begin{example}{岛屿的数量}{回溯}

    给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
    输入:
    \begin{Textcode}
        11110
        11010
        11000
        00000
    \end{Textcode}
    输出: 1
\end{example}
思路：
\begin{enumerate}
    \item DFS搜索：遍历二维数组，对于位置[r,c]处为1的位置（将值设置为0，表示依旧访问过）。以此位置为基础继续上下左右搜索为1的位置当没法找到为1的元素的时候说明dfs已经尝试了所有可能依旧没有找到为1的位置。这时这块区域就是孤岛。
    \item BFS搜索：遍历二维数组，对于位置为[r,c]处为1的位置，进入队列（队列方式实现只是为了减少递归开销）。如果队列中元素不为空，将其上下左右为1的位置记录下来，进入队列。如果队列中元素全部出队说明通过一个节点和其所有连接节点
          已经找不到为1的位置，这时孤岛数+1。
\end{enumerate}

\begin{example}{BFS例子}{打开旋转锁}

\end{example}
思路：
用BFS搜索，如\figref{fig:bfs_unlock}从{0000}开始，因为每个位置可以上下变动，所有可能变动的数量是8个，即从0000能到达的状态有8种（相邻节点）。到达状态后按照每个状态继续搜索直到找到目标状态，注意（0000）可能也是deadend，这样无法返回结果。
\begin{figure}[!htbp]
    \centering
    \includegraphics*[width=0.6\textwidth]{bfs_unlock}
    \caption{初始节点搜索}
    \label{fig:bfs_unlock}
\end{figure}
\chapter{索引}
\begin{definition}[索引]
    在一组记录集合中找到关键码值等于给定值的某个记录,或者找到关键码值符合特定条件的某些记录的过程。
\end{definition}
\textbf{提高检索效率的方法：}
\begin{itemize}
    \item 预排序
    \item 建立索引
    \item 散列技术
\end{itemize}
\begin{definition}[关键码的比较]
    检索运算的主要操作。
\end{definition}
\begin{definition}[平均检索长度(ASL)]
    检索过程中对关键码的平均比较次数，衡量检索算法优劣的时间标准：
    \begin{equation}
        ASL = \sum_{i=1}^nP_iC_i
    \end{equation}
    这里$P_i$为检索第i各院素的概率，$C_i$为找到第i个元素所需要的关键吗值和给定值的比较次数。
\end{definition}
\textbf{顺序检索：}针对线性表里的所有记录,逐个进行关键码和给定值的比较。如果某个记录的关键码和给定值比较相等，则检索成功否则检索失败。可以顺序存储，链接。
\textbf{监视哨顺序检索算法}
\begin{cpp}
    template <typename Type>
    class Item {
            private:
            Type key;   // 关键码域
            // 其它域
            public:
            Item(Type value):key(value) {}
            Type getKey() {return key;}        // 取关键码值
            void setKey(Type k){ key=k;}    // 置关键码
        };
    vector<Item<Type>*> dataList;
    template <typename Type> int SeqSearch(vector<Item<Type>*>& dataList, int
    length, Type k) {
            int i=length;
            dataList[0]->setKey (k);    // 将第0个元素设为待检索值,设监视哨
            while(dataList[i]->getKey()!=k) i--;
            return i;    // 返回元素位置
        }
\end{cpp}
检索成功：假设检索每个关键码等概率$P_i=\frac{1}{n}$
\begin{equation*}
    \sum_{i=0}^{n-1}P_i\cdot(n-i)=\frac{1}{n}\sum_{i=0}^{n-1}(n-i)=\sum_{i=1}^n i=\frac{n+1}{2}
\end{equation*}
检索失败：假设检索失败时都需要比较n+1此（设置了一个监视哨）

假设检索成功的概率为p，检索失败的概率为q=(1-p)
\[ASL=p\cdot\frac{n+1}{2}+q\cdot(n+1)=(n+1)(1-p/2)\]
$(n+1)/2<ASL<(n+1)$
顺序检索的优点：插入元素可以直接加在表尾$\Theta(1)$,缺点：检索时间太长$\Theta(n)$

\begin{definition}[二分检索]
    将任一元素 dataList[i] .Key 与给定值 K 比较。
\end{definition}
三种情况:
\begin{itemize}
    \item Key = K,检索成功,返回 dataList[i]
    \item Key > K,若有则一定排在 dataList[i]前
    \item Key < K,若右则一定排在 dataList[i]后
\end{itemize}
进一步缩小范围。
\begin{cpp}
    template <Typename Type> int BinSearch (vector<Item<Type>*>&
    dataList, int length, Type k){
            int low=1, high=length, mid;
            while (low<=high) {
                    mid=(low+high)/2;
                    if (k<dataList[mid]->getKey())
                    high = mid-1;// 右缩检索区间
                    else if (k>dataList[mid]->getKey())
                    low = mid+1;// 左缩检索区间
                    else return mid;// 成功返回位置
                }
            return 0;    // 检索失败,返回0
        }
\end{cpp}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{index01}
    \caption{二分检索}
\end{figure}
第一次:l=1, h=9, mid=5; array[5]=35>18\\
第二次:l=1, h=4, mid=2; array[2]=17<18\\
第三次:l=3, h=4, mid=3; array[3]=18=18\\
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{index02}
    \caption{}
\end{figure}
二分检索性能分析：
\begin{itemize}
    \item 最大检索长度$\lceil log_2(n+1\rceil)$
    \item 失败检索长度是：$log_2(n+1)$或者$log_2(n+1)$
    \item 成功的平均检索长度为：
          \[ASL=\frac{1}{n}(\sum_{i=1}^j i\cdot2^{i-1})=\frac{n+1}{n}log_2(n+1)-1\approx log_2(n+1)-1\quad(n>50)\]
\end{itemize}
优缺点：
\begin{itemize}
    \item[优点：]平均和最大检索长度相近，检索速度快。
    \item[缺点：]要排序，顺序存储，不容易更新（插入/删除）。
\end{itemize}
\textbf{分块检索的思想}
“按块有序”
\begin{itemize}
    \item  设线性表中共有 n 个数据元素,将表分成 b 块
    \item  前一块最大关键码必须小于后一块最小关键码
    \item  每一块中的关键码不一定有序

\end{itemize}
顺序与二分法的折衷既有较快的检索又有较灵活的更改。
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{index03}
    \caption{分块检索}
\end{figure}
分块检索为两级检索：
\begin{itemize}
    \item 先在索引表中确定待查元素所在的块,$ASL_b$
    \item 然后在块内检索待查的元素,$ASL_w$
\end{itemize}
\[ASL=ASL_b+ASL_w\approx log_2(b+1)-1+(s+1)/2\approx\log_2(1+n/s)+s/2\]

假设在索引表中用顺序检索，在块内也使用顺序检索：
\begin{align}
    ASL_b=\frac{b+1}{2}                                \\
    ASL_w=\frac{s+1}{2}                                \\
    ASL & =\frac{b+1}{2}+\frac{s+1}{2}=\frac{b+s}{2}+1 \\
        & =\frac{n+s^2}{2s}+1
\end{align}
当$s=\sqrt{n}$时ASL取最小值：$ASL=\sqrt{n}+1\approx\sqrt{n}$。当 n=10,000 时：
\begin{itemize}
    \item 顺序检索 5,000 次
    \item 二分法检索 14 次
    \item 分块检索 100 次
\end{itemize}
\textbf{分块检索优缺点：}
优点:插入、删除相对较易。没有大量记录移动。 缺点:增加一个辅助数组的存储空间。初始线性表分块排序。当大量插入/删除时,或结点分布不均匀时，速度下降。
\subsection{集合检索}
\begin{definition}[集合(set)]:由若干个确定的、相异的对象(element)构成的整体。
\end{definition}
\begin{definition}[集合的检索：]确定一个值是不是某一个集合的元素。
\end{definition}
\begin{table}[H]
    \centering
    \begin{tabular}{llll}
        \toprule
                                      & {运算名称} & 数学符号    & 计算机运算符号 \\
        \midrule
        \multirow{5}{2cm}{算术运算符} & 并         & $\cup$      & *,\&,AND       \\
                                      & 差         & -           & -              \\
                                      & 交         & $\cap$      & $*,\&AND$      \\
                                      & 相等       & =           & 并==           \\
                                      & 不等       & $\neq$      & $!=$           \\
        \midrule
        \multirow{5}{2cm}{逻辑运算}   & 包含于     & $\subset$   & <=             \\
                                      & 包含       & $\supseteq$ & >=             \\
                                      & 真包含于   & $\subset$   & <              \\
                                      & 真包含     & $\subset$   & >              \\
                                      & 属于       & $\in$       & IN,at          \\
        \bottomrule
    \end{tabular}
\end{table}
\textbf{集合的抽象数据类型}
\begin{cpp}
    template<size_t N>// N为集合的全集元素个数
    class mySet {
    public:
    mySet() ;// 构造函数
    mySet(ulong X);
    mySet<N>& set();// 设置元素属性
    mySet<N>& set(size_t P, bool X = true);
    mySet<N>& reset();// 把集合设置为空
    mySet<N>& reset(size_t P);// 删除元素P
    bool at(size_t P) const;// 属于运算
    size_t count() const;// 集合中元素个数
    bool none() const;// 判断是否空集
    bool operator==(const mySet<N>& R) const;  //等于
    bool operator!=(const mySet<N>& R) const;  //不等于
    bool operator<=(const mySet<N>& R) const;  //包含于
    bool operator<(const mySet<N>& R) const;  //真包含于
    bool operator>=(const mySet<N>& R) const;  //包含
    bool operator>(const mySet<N>& R) const;  //真包含
    friend mySet<N>operator&(const mySet<N>&L,const mySet<N>&R);//交
    friend mySet<N>operator|(const mySet<N>&L,const mySet<N>&R);//并
    friend mySet<N>operator-(const mySet<N>&L,const mySet<N>&R);//差
    friend mySet<N>operator^(const mySet<N>&L,const mySet<N>&R);//异或
\end{cpp}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{set01.png}
    \caption{用位向量表示集合}
\end{figure}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{set02.png}
    \caption{计算0-15之间的素奇数}
\end{figure}
\begin{cpp}
    typedef unsigned long ulong;
    enum {
            // unsigned long数据类型的位的数目
            NB = 8 * sizeof (ulong),
            // 数组最后一个元素的下标
            LI = N == 0 ? 0 : (N - 1) / NB
        };
    // 存放位向量的数组
    ulong A[LI + 1];
\end{cpp}
设置集合元素
\begin{cpp}
    template<size_t N>
    mySet<N>& mySet<N>::set(size_t P, bool X) {
            if (X)  // X为真,位向量中相应值设为1
            A[P / NB] |= (ulong)1 << (P % NB);
            // P对应的元素进行按位或运算
            else A[P / NB] &= ~((ulong)1 << (P % NB));
            // X为假,位向量中相应值设为0
            return (*this);
        }
\end{cpp}
集合的交运算(\&)
\begin{cpp}
    template<size_t N>
    mySet<N>& mySet<N>::operator&=(const mySet<N>& R)
    { // 赋值交
            for (int i = LI; i >= 0; i--)// 从低位到高位
            A[i] &= R.A[i];    // 以ulong元素为单位按位交
            return (*this);
        }
    template<size_t N>
    mySet<N> operator&(const mySet<N>& L, const mySet<N>& R)
    { //交
            return (mySet<N>(L) &= R);
        }
\end{cpp}
\subsection{散列检索}
散列方法的发现得益于计算机寻址，通过将节点的关键码K通过函数h映射为h(K),h(k)为节点存储的位置。检索的时候也是根据这个函数计算其存储位置。通常散列表的存储是一个一维数组，散列地址是数组的下标。

\textbf{例如：}已知线性表的关键码集合为：
\begin{Textcode}
    S = {and,array,begin,do,else,end,for,go,if,repeat,then,util,while,while}
\end{Textcode}
可设散列表为：char HT2[26][28]。散列函数H(key)的值，取关键码key中的第一个字母在字母表\{a,b,c,...2\}中的序号，即：H(Key) = key[0]-'a'
\begin{table}[H]
    \centering
    \begin{tabular}{cccc}
        \toprule
        散列地址 & 关键码      & 散列地址 & 关键码       \\
        \midrule
        0        & (and,array) & 13       &              \\
        1        & begin       & 14       &              \\
        2        &             & 15       &              \\
        3        & do          & 16       &              \\
        4        & (end,else)  & 17       & repeat       \\
        5        & for         & 18       &              \\
        6        & go          & 19       & then         \\
        7        &             & 20       & util         \\
        8        & if          & 21       &              \\
        9        &             & 22       & (while,with) \\
        10       &             & 23       &              \\
        11       &             & 24       &              \\
        12       &             & 25       &              \\
        \bottomrule
    \end{tabular}
\end{table}
\begin{cpp}
    // 散列函数的值为key中首尾字母在字母表中序号的平均值,即:
    int H3(char key[])
    {
            int i = 0;
            while ((i<8) && (key[i]!='\0')) i++;
            return((key[0] + key(i-1) - 2*'a') /2 )
        }
\end{cpp}
\begin{table}[H]
    \centering
    \begin{tabular}{cccc}
        \toprule
        散列地址 & 关键码 & 散列地址 & 关键码 \\
        \midrule
        0        &        & 13       & while  \\
        1        & and    & 14       & with   \\
        2        &        & 15       & util   \\
        3        & end    & 16       & then   \\
        4        & else   & 17       &        \\
        5        &        & 18       & repeat \\
        6        & if     & 19       & t      \\
        7        &        & begin    &        \\
        8        & do     & 21       &        \\
        9        &        & 22       &        \\
        10       & go     & 23       &        \\
        11       & for    & 24       &        \\
        12       & array  & 25       &        \\
        \bottomrule
    \end{tabular}
\end{table}
\begin{definition}[负载因子：]$\alpha=\frac{n}{m}$,散列表的空间大小为m，填入表中的节点数为n。
\end{definition}
\begin{definition}[冲突：]
    某个散列函数对于部相关的关键码计算出了相同的散列地址。
\end{definition}
\begin{definition}[同义词：]发生冲突的两个关键码。
\end{definition}
\begin{definition}[散列函数：]把关键码值映射到存储位置的函数，通常用h表示。Address=Hash(key)
\end{definition}
散列函数的选取原则：
\begin{itemize}
    \item 运算经可能简单。
    \item 函数的值域必须在表长的范围内。
    \item 尽可能使得关键码不同是，散列函数值不同。
\end{itemize}
需要考虑的因素主要有：关键码长度，散列表大小，关键码分布情况，记录的检索频率。
常用的散列函数选取法：
\begin{itemize}
    \item  除余法
    \item 乘余取整法
    \item 平方取中法
    \item 数字分析法
    \item 基数转换法
    \item 折叠法
    \item ELFhash 字符串散列函数
\end{itemize}
\begin{definition}[除余法：]用关键码x除以M(往往取散列表长度)，并取余数作为散列地址。散列函数为：
    \[h(x)=x\ mod\ M\]
\end{definition}
通常选择一个\textcolor{red}{质数}作为M的值,函数值依赖于自编两x的所有位，不仅仅是最右边k个低位，增大了均匀分布的可能性。M不用偶数，因为如果M设置为偶数：
\begin{itemize}
    \item x是偶数，h(x)也是偶数。
    \item x是奇数，h(x)也是奇数。
\end{itemize}
这样容易导致分布不均匀，因为如果偶数关键码比奇数关键码出现的概率大，那么函数值就不能均匀分布了，反之亦然。
M也不用冪：
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{hash01}
    \caption{幂作为M}
\end{figure}
若把 M 设置为 2 的幂，那么,h(x)=x mod 2 k 仅仅是 x (用二进制表示)最右边的k个
位(bit)。 若把 M 设置为 10 的幂那么,h(x)=x mod 10 k 仅仅是 x (用十进制表示)最右边的 k
个十进制位(digital)
\textcolor{red}{该散列函数的缺点}:散列值不依赖于x 的全部比特位。
除余法面临的问题：连续的关键码映射成连续的散列值，虽然能保证连续的关键码不发生冲突，但也意味着要占据连续的数组单元。 可能导致散列性能的降低。

\textbf{乘余取整法}
\begin{itemize}
    \item 让关键码key乘上一个常熟A(0<A<1),提取其乘积的小数部分。
    \item 用整数n乘上这个值，对结果向下取整，把它作为散列地址。
\end{itemize}
散列函数为：
\[hash(key)=\lfloor n\cdot(A\cdot key\%1\lfloor)\]
其中$A\cdot key\%1$表示$A\cdot key$小数部分：$A\cdot key\%1=A*key-\lfloor A\cdot key\rfloor$
\begin{example}[乘余取整法例子]
    设关键码key = 123456,n = 10000且取$A=\sqrt{5}-1$/2=0.618,因此有：
    \begin{align*}
        has(123456) & =                                                  \\
                    & =\lfloor 1000\cdot(0.6180339\cdot123456\%1)\rfloor \\
                    & =\lfloor10000\cdot(76300.0041445\ldots\%1)         \\
                    & =41
    \end{align*}
\end{example}
乘余取整法参数取值：
\begin{itemize}
    \item 若地址空间为p位，就取$n=2^p$
          \begin{itemize}
              \item 所求的散列地址正好是计算出来的
              \item $A\cdot key\%1=A\cdot key-\lfloor A\cdot key\rfloor$值的小数点左p bit值
          \end{itemize}
\end{itemize}
该方法的有点是：n的选择无关紧要。A可以取任何值，和待排序的数组特征有关。一般情况下取黄金分割最理想。

\textbf{平方取中法}\\
\begin{definition}[平方取中法]
    先通过关键码的平方扩大差别，再去其中的几位或者其组合作为散列地址。
\end{definition}
\begin{example}[例子]
    \begin{itemize}
        \item 二进制关键码:00000100,00000110,000001010,000001001,000000111
        \item 平方结果为：00010000,00100100,01100010,0101000，1,00110001
        \item 如果表长为4个二进制位，则可取中间四位作为散列地址：（0100,1001,1000,0100,1100）
    \end{itemize}
\end{example}
\textbf{数字分析法}
设有n个d位数，每一位可能有r中不同的符号，这r中不同的符号在各位上出现的频率不一定相同：
\begin{itemize}
    \item 可能在某些位上分布均匀写，每种符号出现的概率均等。
    \item 在某些位上分布不均匀，只有某集中符号经常出现。
\end{itemize}
可根据散列表的大小，选取其中各个符号分布均匀的若干为作为散列地址。各位数字中符号分布的均匀度$\lambda_k$
\[\lambda_k=\sum_{i=1}^r(\alpha_i^k-\frac{n}{r})^2\]
$\alpha_i^k$表示第i个符号在第k位上出现的次数，$\frac{n}{3}$表示各种符号在n个数中均匀出现的期望值。$\lambda_k$越小，表明该位（第k位）各种符号分布的越均匀。

数字分析法仅适用于事先明确知道表中所有关键码每一位熟知的帆布情况，它完全以来与关键码集合。如果换一个关键码集合，选择那几位数据要重新决定。

\textbf{奇数转换法} \\
把关键码看成是另一进制上的数后再把它转化成原来进制上的数，取其中若干位作为散列地址，一般取大于原来奇数的数作为转换的奇数，并且两个奇数要互质。

\begin{example}[奇数转换法]
    给定一个十进制数的关键码$(210485)_{10}$，把它看成以13为基数的13进制数$(210485)_13$，再把它转化成十进制：
    \begin{align}
        (210485)_{13} & =                                                    \\
                      & =2\times 13^5+1\times 13^4+4\times 13^2+8\times 13+5
                      & =(771932)_{10}
    \end{align}
    假设散列表长度为10000,可以取低四位1932作为散列地址。
\end{example}
\textbf{折叠法}\\
关键码所含的位数很多，采用平方取中法计算太复杂，使用折叠法：将关键码分割成位数相同的及部分（最有一部分的位数可以不同），然后取这及部分的叠加和（舍去进位）作为散列地址。有两种叠加方法：
\begin{itemize}
    \item 移位叠加：把各部分的最后一位对齐相加。
    \item 分割叠加：个部分不折断，沿着个部分的分解来回折叠，然后对齐相加，将相加的结果作为散列地址。
\end{itemize}
如果一本书的编号为04-42-20586-4
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{hash_fold.png}
    \caption{折叠法}
\end{figure}
\textbf{ELFlash字符串散列函数}
用于UNIX系统V4.0"可执行链接格式"：
\begin{cpp}
    int ELFhash(char* key) {
            unsigned long h = 0;
            while(*key) {
                    h = (h << 4) + *key++;
                    unsigned long g = h & 0xF0000000L;
                    if (g) h ^= g >> 24;
                    h &= ~g;
                }
            return h % M;
        }
\end{cpp}
长字符串和短字符串都很有效，字符串中每个字符都有相同的作用，对于散列表中的位置不可能删生不平均的分布。

\emph{若关键码不是整数而是字符串时,可以把每个字符串转换成整数,再应用平方取中法}

\subsection{开散列法}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{hash_open.png}
    \caption{拉链法}
\end{figure}
表中空单元其实应该有特殊之标记出来，例如使用-1或者INFINITY或者散列表中的内容就是指针，空单元则内容为空指针。

\textbf{拉链法性能分析}
给定一个大小为M存储n个记录的表：散列函数（在理想情况下）将把记录在表中M个位置平均放置，使得平均每一个链表中有n/M个记录。M>n时，散列方法的平均代价为$\Theta(1)$。
\subsection{闭散列法}
$d_0 =h(K)$称为 K 的基地址
\begin{itemize}
    \item 当冲突发生时,使用某种方法为关键码K生成一个散列地址序列                                           $d_1 ,d_2 ,\ldots d_i ,... , d_{m-1}$所有 $d_i (0<i<m)$ 是后继散列地址
    \item 形成探查的方法不同,所得到的解决冲突的方法也不同
    \item 插入和检索函数都假定每个关键码的探查序列中至少有一个存储位置是空的，否则可能会陷入一个无限循环中，也可以限制探查序列长度。
\end{itemize}
\subsubsection{线性探查法}
基本思想：如果记录的基位置存储位置被占用,那么就在表中下秱,直到找到一个空存储位置，依次探查下述地址单元：$d+1,d+2,......,M-1,0,1,\ldots,d-1$用于简单线性探查的探查函数是:$P(K,i)=i$。线性探查的优点：表中所有的存储位置都可以作为插入新纪录的候选位置。
\begin{table}[H]
    \centering
    \begin{tabular}{lllllllllllllll}
        \toprule
        0  & 1  & 2  & 3  & 4  & 5  & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\
        \midrule
        26 & 25 & 41 & 15 & 68 & 44 & 6 & 0 & 0 & 0 & 36 & 0  & 38 & 12 & 51 \\
        \bottomrule
    \end{tabular}
\end{table}
因为是线性探查，于对位置11,可能出现该位值是空，插入概率1/15,可有可能10冲突插入11,总计概率为2/15,同理放入到7的概率为11/15。改进线性探查，每次跳过常数c而不是1个槽，探查序列中的第i个槽是$(h(K)+ic) mod M$，基位置相邻的记录就不会进入同一个探查序列乐。探查函数是$p(K,i)=ic$,c和M必须是互为素数。

\subsubsection{二次探查}
探查增量序列地址为:$1^2,-1^2,2^2,-2^2,\ldots$,即地址公式为：
\begin{equation*}
    \begin{split}
        d_{2i-1}=(d+i^2)%M\\
        d_{2i}=(d-i^2)%M
    \end{split}
\end{equation*}
用于简单线性探查的探查函数是：
\begin{equation*}
    \begin{split}
        P(K,2i-1)=i^2\\
        p(K,2i)=-i^2
    \end{split}
\end{equation*}
\begin{remark}
    简单将就是如果地址冲突就线加上$1^2$如果依旧冲突就减去$1^2$(为负就往表后面找)，还冲突就加上$2^2$，还冲突就减去$-2^2$依次直到找到地方放为止。
\end{remark}
\subsubsection{伪随机数序列探查}
查看函数$p(K,i)=perm[i-1]$,这里perm是一个长度为M-1的数组，包含值从1到M-1的随机序列。
\begin{cpp}
    //产生n个数的伪随机排列
    void permute(int *array,int n)
    {
    for(int i=0lu<=n;i++)
    swap(array[i-1],array[Random(i)])
    }
\end{cpp}

二次聚集
\begin{itemize}
    \item 消除基本聚集：基地之不同的关键码，其探查序列有所重叠，伪随机探查和二次探查可以消除。
    \item 二次聚集：两个关键码散列到同一个基地之，还是得到同样的严查序列，所产生的聚集，原因是探查序列只是基地址的函数而不是原来关键码值的函数。
\end{itemize}
\subsubsection{双散列探查法的基本思想}
双散列探查法使用两个散列函数$h_1$和$h_2$，若在地址$h_1(key)=d$发生冲突，在计算$h_2(key)$得到的探查序列为：
\[(d+h_2(key))\%M,(d+2h)2(key))\%M,(d+3h_2(key))\%M,\ldots\]
$h_2(key)$尽量和M互为素数，是发生冲突的同义词地址均匀分布在整个表中，否则可能造成同义词地址的循环计算。优点是不易产生聚集。缺点是计算量增大。

\textbf{M和$h_2(k)$的选择方法}
\begin{itemize}
    \item 方法1：选择M为一个素数，$h_2$返回的值在$1\leq h_2(K)\leq M-1$范围之内。
    \item 方法2：设置$M=2^m$，让$h_2$返回一个1到$2^m$之间的奇数值。
    \item 方法3：若M是素数，$h_1(K) = K mod M$,$h_2(k)=k\ mod(M-2)+1$或者$h_2(K)=K\ mod(M-2) +1$.
    \item 方法4：若M是任意数，$h_1(K)=K\ mod\ p$(p是小于M的最大素数)。$h_2(K)=K\ mod\ q+1$(q是小于p的最大素数。)
\end{itemize}
\section{图}
\subsection{图的相关定义}
\begin{definition}[图的定义]
    G=(V,E),V是顶点vertex集合，E是边edge的集合。
\end{definition}
\begin{definition}[完全图：]顶点之间两两有边。
\end{definition}
\begin{definition}[稀疏图：]边的条数小于完全图的5\%。
\end{definition}
\begin{itemize}
    \item 无向图：A-B和B-A相同。
    \item 有向图：边之间是有向的.如下：$v_1->v_4$有边，$v_4-v_1$不直接关联。
\end{itemize}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{graph_no_direction}
    \label{fig:graph_no_direction}
    \caption{无向图}
\end{figure}
带权图如\figref{fig:graph_with_weight}：
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{graph_with_weight}
    \caption{带权图}
    \label{fig:graph_with_weight}
\end{figure}
入度：指向节点的边数。出度：指出节点的边。
\begin{definition}[子图：]
    图$G(V,E),G'(V',E')$中，如果$V'\leq V,E'\leq E$并且$E'$中的边所关联的顶点都在$V'$中，则称$G'$是$G$的子图。
\end{definition}
从顶点$V_p$到顶点$V_q$的路径，顶点序列$V_p,V_{i1},V_{i2},\ldots,V_{in},V_{q}$使得$(V_p,V_{i1}),(V_{i1},v_{i2}),\ldots ,(V_{in},V_q)$（若对有向图，则使得$<V_p,V_{i1}>,<V_{i1},V_{i2}>,\ldots,<V_{in},V_q>$）都在E中。
如果路径可以表示为$v_1v_2,v_3,\ldots,v_{n-1},v_n$，如果$v_1=v_n$，且没有重复的边，那么此路径称为\textbf{环}。\textcolor{red}{无向图路径长度大于等于3}。
\begin{definition}[有根图]
    一个有向图中，若存在一个顶点$V_0$，从此顶点有路径可以到达途中其它所有顶点，则称此有向图为有根的图，$V_0$是图的根。
\end{definition}
\begin{definition}[连通性]
    对于无向图$G(V,E)$而言，如果从$V_1$到$V_2$有一条路经（从$V_2$到$V_1$也一定有一条路经），则称$V_1$和$V_2$是连通的。
\end{definition}
\begin{definition}[强连通]
    有向图$G(V,E)$如果两个顶点$v_i,v_j$间有一条$v_i$到$v_j$的有向路径，同时还有一条$v_j$到$v_i$的有向路径，则称两个顶点强连通。
\end{definition}
\begin{definition}[强连通分量]
    非强连通图有向图的极大强连通子图，称为强连通分量。
\end{definition}
图的抽象数据类型：
\begin{cpp}
    class Graph{
            public:
            int VerticesNum();//返回图的顶点个数
            int EdgesNum()://返回边的个数
            Edge FirstEdge(int oneVertex);//第一条关联边
            Edge NextEdge(Edge preEdge);//下一条兄弟边
            bool setEdge(int fromVertex,int toVertex,int weight);//添加一条边
            bool delEdge(int fromVertex,int toVertex);//删除边
            bool IsEdge(Edge oneEdge);//判断oneEdge是不是边
            int FromVertex(Edge oneEdge);//返回边的终点
            int ToVertex(Edge oneEdge);//返回边的终点
            int Weight(Edge oneEdge);//返回边的权
        };
\end{cpp}
\begin{definition}[邻接矩阵]
    表示顶点之间的邻接关系，即有没有边。设$G=<V,E>$是一个n个顶点的图，则图的相邻矩阵是一个二位数组A[n,n],定义如下：
    \begin{equation*}
        A[i,j]=
        \begin{cases}
            1,\quad \text{若}(V_i,V_j)\in E\text{或者}<V_i,V_j>\in E \\
            0,\quad \text{若}(V_i,V_j)\notin E\text{或者}<V_i,V_j>\notin E
        \end{cases}
    \end{equation*}
\end{definition}
对于n个顶点的图，邻接矩阵的空间代价都为$(n^2)$和边数无关。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{dg5}
    \caption{有向图的邻接矩阵}
\end{figure}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{dg6}
    \caption{无向图的邻接矩阵}
\end{figure}
邻接矩阵的类定义：
\begin{cpp}
    class Edge {// 边类
            public:
            int from,to,weight;// 边的始点, 终点, 权
            Edge() { // 缺省构造函数
                    from = -1; to = -1; weight = 0; }
            Edge(int f,int t,int w){// 给定参数的构造函数
                    from = f; to = t; weight = w;
                }
        };
    class Graph {
            public:
            int numVertex; // 图中顶点的个数
            int numEdge;// 图中边的条数
            int *Mark; // 图的顶点访问标记
            int *Indegree; // 存放图中顶点的入度
        };
\end{cpp}
\begin{definition}[稀疏因子]
    在$m\times n$的矩阵中，有t个非零元素，则稀疏因子$\delta$为：\[\delta = \frac{t}{m\times n}\]如果$\delta$小于0.05,则可认为是稀疏矩阵。
\end{definition}
对于稀疏图,可以采用邻接表存储法：
\begin{itemize}
    \item 边较少,相邻矩阵就会出现大量的零元素
    \item 相邻矩阵的零元素将耗费大量的存储 空间 和 时间
\end{itemize}
邻接表 ( adjacency list ) 链式存储结构:
\begin{itemize}
    \item  顶点表目有两个域:顶点数据域和指向此顶点边表指针域
    \item  边表把依附于同一个顶点 $v_i$的边(即相邻矩阵中同一行,的非0元素)组织成一个单链表。由两个主要的域组成:
    \item  与顶点 $v_i$ 邻接的另一顶点的序号
    \item      指向边表中下一个边表目的指针
\end{itemize}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{adj_node}
    \caption{链式邻接表的顶点和边}
    \label{adj_node}
\end{figure}
\emph{无向图同一条边在邻接表中出现两次}

\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{adj_table}
    \caption{无向图的邻接表}
    \label{fig:adj_table}
\end{figure}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{adj_node_weight_ast}
    \label{fig:adj_node_weight_ast}
    \caption{带权图邻接表表示}
\end{figure}
表头数据结构定义如下：
\begin{cpp}
    class VNode {
            public:
            int data;
            ArcNode* firstarc;
            VNode(int d,ArcNode* fp);
            VNode(int d);
        };
\end{cpp}
表中节点结构：
\begin{cpp}
    class ArcNode {
            public:
            int adjvex;
            ArchNode *nextarc;
            int info;
            ArcNode(int adj, int i, ArchNode *ap);
            ArcNode(int adj, int i);
        };
\end{cpp}

\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{graph_adj_table}
    \caption{出入度分别表示}
\end{figure}
图邻接表的空间代价：
n 个顶点e条边的无向图,需用 (n + 2e) 个存储单元，n 个顶点 e 条边的有向图需用 (n + e) 个存储单元。
当边数e 很小时,可以节省大量的存储空间，边表中表目顺序往往按照顶点编号从小到大排列。

\textbf{十字链表 (Orthogonal List)} 可以看成是邻接表和逆邻接表的结合,
对应于有向图的每一条弧有一个表目,共有5个域:头 headvex、尾 tailvex 、下一条共尾弧 tailnextarc;下一
条共头弧 headnextarc;弧权值等 info 域。顶点表目由3个域组成:data 域;firstinarc 第一条以该顶点为终点的弧;firstoutarc 第一条以该顶点为始点的弧。

稀疏矩阵的十字链表由行和列的指针序列。每个结点都包含两个指针:同一行的后继,同一列的后继。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{dg11}
    \caption{稀疏矩阵的十字链表}
\end{figure}
\subsection{图的遍历}
\begin{definition}[图的遍历]
    给出一个图G和其中任意一个顶点$V_0$,从$V_0$出发系统地访问G中所有的顶点,每个顶点访问而且只访问一次
\end{definition}
从一个顶点出发,试探性访问其余顶点,同时必须考虑到下列情况：
\begin{itemize}
    \item 从一顶点出发,可能不能到达所有其它的顶点。如：非连通图。
    \item 也有可能会陷入死循环。如：存在回路的图
\end{itemize}
解决的办法是：为每个顶点保留一个 标志位 (mark bit)，算法开始时,所有顶点的标志位置零。 在遍历的过程中,当某个顶点被访问时,其标志位就被标记为已访问。
图遍历的算法框架：
\begin{cpp}
    void graph_traverse(Graph * G)
    {
            for(int i=0;i<G.VerticesNum();i++)
            G.Mark[i] = UNVISITED;//检查图的所有顶点是否被标记过，如果没有则从未标记的顶点开始继续遍历
            for(int i=0;i<G.VerticesNum();i++)
            if(G.Mark[i] == UNVISITED)
            do_traverse(G,i);
        }
\end{cpp}
\textbf{深度优先遍历DFS}：类似于树的先根次序遍历,尽可能先对纵深方向进行搜索。
\begin{itemize}
    \item 选取一个未访问的点 $v_0$作为源点。
    \item 访问顶点 $v_0$。
    \item 递归地深搜遍历$v_0$ 邻接到的其他顶点。
    \item 重复上述过程直至从 $v_0$ 有路径可达的顶点都已被访问过。
    \item 再选取其他未访问顶点作为源点做深搜,直到图的所有顶点都被访问过。
\end{itemize}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{graph_dfs}
    \label{fig:graph_dfs}
    \caption{深度优先搜索}
\end{figure}
搜索顺序为:$a\rightarrow b\rightarrow c\rightarrow f\rightarrow d\rightarrow e\rightarrow g$

图深度优先遍历DFS：
\begin{cpp}
    void DFS(Graph & G,int v){ //深度优先搜索的递归实现
            G.Mark[v] = VISITED;//标记为设置为VISITED
            Visit(G,v);//访问顶点v
            for(Edge e = G.FristEdge(V);G.IsEdge(e);e=G.NextEdge(e))
            if(G.Mark[G.ToVertex(e)] == UNIVISTED)
            DFS(G,G.ToVertex(e));
            PostVIsit(G,v);//对顶点v的后访问
        }
\end{cpp}
\textbf{广度优先遍历（BFS}）：其遍历过程是从图中的某一个顶点$v_0$出发，访问并标记顶点$v_0$之后一层层横向搜索$v_0$的所有邻接点，对这些临界点一层层横向搜索，知道$v_0$有路径可达的顶点都已经被访问过。在选取其它没有访问的顶点作为远点广搜，知道所有点都被访问过。
\begin{cpp}
    void BFS(Graph & G,int v)
    {
            using std::deque;
            queue<int> Q;
            Visit(G,v);//访问顶点
            G.Mark[v] = VISITED;//标记
            Q.push(v);//进入队列
            while(!Q.empty()){//如果队列不为空
                    int u = Q.front();//获得队列顶部元素
                    Q.pop();//顶部元素出队
                    for(Edge e = G.FirstEdge(u);G.IsEdge(e);e=G.NextEdge(e))
                    if(G.Mark[G.ToVertex(e) == UNVISITED])
                    {
                            Visit(G,G.ToVertex(e));
                            G.Mark[G.ToVertex(e)] = VISITED;
                            Q.push(G.toVertex(e));
                        }
                }
        }
\end{cpp}
图搜索的时间复杂度：DFS 和 BFS 每个顶点访问一次,对每一条边
处理一次 (无向图的每条边从两个方向处理)采用邻接表表示时,有向图总代价为$\Theta(n+e)$,无向图为$\Theta(n+2e)$。采用相邻矩阵表示时,处理所有的边需要 $\Theta(n^2)$的时间 ,所以总代价为$\Theta(n+n^2)=\Theta(n^2)$
\textbf{拓扑排序}：对于 有向无环图 $G= (V,E) ,V $里顶点的线性序列称作一个 \textcolor{red}{拓扑序列},该顶点序列满足:
\begin{itemize}
    \item 若在有向无环图 $G$ 中从顶点 $v_i$ 到$v_j$有一条路径,则在序列中顶点 $v_i$ 必在顶点 $v_j$ 之前
\end{itemize}
\textbf{拓扑排序 (topological sort)}：将一个 \textcolor{red}{有向无环图}中所有顶点在不违反 先决条件关系的前提下排成线性序列的过程称为\textcolor{red}{拓扑排序}

\begin{table}[!htbp]
    \centering
    \caption{大学课程信息}
    \begin{tabular}{ccc}
        \toprule
        课程代号 & 课程名称   & 先修课程  \\
        \midrule
        $C_1$    & 高等数学   &           \\
        $C_2$    & 程序设计   &           \\
        $C_3$    & 离散数学   & $C_1,C_2$ \\
        $C_4$    & 数据结构   & $C_2,C_3$ \\
        $C_5$    & 算法分析   & $C_2$     \\
        $C_6$    & 编译技术   & $C_4,C_5$ \\
        $C_7$    & 操作系统   & $C_4,C_9$ \\
        $C_8$    & 普通物理   & $C_1$     \\
        $C_9$    & 计算机原理 & $C_8$     \\
        \bottomrule
    \end{tabular}
\end{table}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{topocourse}
    \caption{大学课程拓扑排序}
\end{figure}
\textcolor{red}{拓扑排序的方法}：
任何 有向无环图 (DAG) ,其顶点都可以排在一个拓扑序列里,其拓扑排序的方法是:
\begin{enumerate}
    \item 从图中选择任意一个入度为0的顶点且输出之。
    \item 从图中删掉此顶点及其所有的出边,将其入度减少1。
    \item 回到第 (1) 步继续执行。
\end{enumerate}
\textcolor{red}{队列实现的图拓扑排序}：
\begin{cpp}
    void TopsoetbyQueue(Graph & G){
            for(int i=0;i<G.VerticesNum();i++)
            G.Mark[i] = UNVISITeD;
            using std::queue;
            queue<int> Q;
            for(i=0;i<G.VerticesNum();i++)
            if(G.Indegree[i] == 0)
            Q.push()
            while(!Q.empty())
            {
                    int v = Q.front();
                    Q.pop();
                    Visit(G,v);
                    G.Mark[v] = VISITED;
                    for(Edge e=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(w))
                    {
                            G.Indegree[G.ToVertex(e)]--;//相邻顶点的入度减一
                            if(G.Indegree[G.ToVertex(e) == 0])//顶点入度减为0则入队
                            Q.push(G.ToVertex(e));
                        }
                }
            for(int i=0;i<G.VerticesNum();i++)
            if(G.Mark[i] == UNVISITED)
            {
                    cout<<"此图有环"<<endl;
                    break;
                }
        }
\end{cpp}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{dg15}
    \caption{课程拓扑排序的拓扑序列}
\end{figure}
\textcolor{red}{深度优先搜索实现的拓扑排序}
\begin{cpp}
    int *TopsortbyDFS(Graph & G)
    {
    for(int i=0;i<G.VerticesNum();i++)
    G.Mark[i] = UNVISITED;
    int *result = new int[G.VerticesNum()];
    int index = 0;
    for(i = 0;i<G.VerticesNum();i++){//对所有顶点
            Do_topsort(G,i,result,index);//递归函数
        }
    for(i=G.VerticesNum()-1;i>=0;i++)//逆序输出
    Visit(G,Result[i]);
    return result;
    }
\end{cpp}
\textcolor{red}{拓扑排序的递归函数}：
\begin{cpp}
    void Do_topsort(Graph & G,int V,int *result,int & index)
    {
            G.Mark[V] = VISITED;
            for(Edge e = G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(w))
            {
                    if(G.Mark[G.ToVertex(e)] == UNVISITED)
                    Do_topsort(G,G.ToVertex(e),result,index);
                }
            result[index++] = V;//后处理
        }
\end{cpp}
\textbf{拓扑排序的时间复杂度：}
与图的深度优先搜索方式遍历相同：图的每条边处理一次，图的每个顶点访问一次。采用邻接表表示时,为$\Theta(n+e)$，采用相邻矩阵表示时,为$\Theta(n^2)$。

是否支持:有向图、无向图，有回路的图，非连通图，权值为负。

\subsection{最短路径}
\begin{definition}[单源最短路径(single-source shortest paths)]给定带权图 $G = <V,E>$,其中每条边 $(v_i ,v_j )$ 上的权$W[v_i ,v_j ] $是一个 非负实数 。计算从任给的一个源点 s   到所有其他各结点的最短路径。
\end{definition}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{graph_sssp}
    \label{fig:graph_sssp}
    \caption{带权图的最短路径}
\end{figure}
\textbf{Dijkstra算法的基本思想：}把所有结点分成两组，第一组 U 包括已确定最短路径的结点。第二组 V–U 包括尚未确定最短路径的结点已标记，按最短路径长度递增的顺序逐个把第二组的结点加到第一组中，直至从 s 出发可达结点都包括进第一组中。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{Dijkstra_process}
    \caption{Digkstra处理}
    \label{fig:Dijkstra_process}
\end{figure}
Dijkstra算法例子：
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{dg18}
    \caption{Dijkstra}
\end{figure}
从$V_0$出发，可选路径$V_1,V_2$,因为$V_2$路径的权值小，选择$V_2$,，$V_2$可选路径为$V_3$,($V_0$访问过了)，选择$V_3$,依次选择权重最小的边直到结束。
Dijkstra算法：
\begin{cpp}
    class Dist{
            public:
            int index;//节点的索引值，仅Dijkstra用的导
            int length;//当前最短路径长度
            int pre;//路径最后经过的节点
        };
    void Dijkstra(Graph& G,int s,Dist * &D)//s是源点
    {
    D = new Dist[G.VerticesNum()];
    for(int i=0;i<G.VerticesNum();i++)
    {
            D[i].index = i;
            D[i].length = INFINITE;
            D[i].pre = s;
        }
    D[s].length = 0;//源点到自身的路径长度设置为0
    MiniHeap<Dist>H(G.EdgesNum());//最小堆用于找出最短路径
    H.Insert(D[s]);
    }
    for(i = 0;i<G.VerticesNum();i++)
    {
            bool FOUND = false;
            Dist d;
            while(!H.isEmpty()){
                    d = H.RemoveMin();
                    if(G.Mark[d.index]) == UNIVISTED{
                            FOUND = true;
                            break;
                        }
                }
            if(!FOUND)
            break//若没有符合条件的最短路径则跳出本次循环
            int v = d.index;
            G.Mark[v] = VISITED;//将标记为设置为VISiTED//将标记位设置为VISITED
            for(Edge e = G.FristEdge(y);G.IsEdge(e);e = G.NextEdge(e))//刷新最短路
            D[G.ToVertex(e)].length = (D[v].length+G.Weight(e));
            D[G.ToVertex(e)].pre = v;
            H.Insert(D[G.ToVertex(e)]);
        }
\end{cpp}
Dijkstra算法时间代价分析：每次改变D[i].length，不删除,添加一个新值(更小的),作为堆中新元素。旧值被找到时,该结点一定被标记为VISITED,从而被忽略。在最差情况下,它将使堆中元素数目由
$\Theta(|V|)$增加到$\Theta(|E|)$,总的时间代价$\Theta((|V|+|E|)log|E|)$。\textcolor{red}{Dijkstra算法不支持负权值}。即使不存在负的回路,也可能有在后面出现的负权值,从而导致整体计算错误。主要原因是 Dijkstra 算法是贪心法,当作最小取进来后,不会返回去重新计算。

\subsubsection{Bellman-Ford算法}
用相邻矩阵 adj 来表示带权有向图。基本思想:
\begin{itemize}
    \item 初始化 $adj^{(0)}$ 为相邻矩阵 adj
    \item 在矩阵 $adj^{(0)}$上做 n 次迭代,递归地产生一个矩阵序列$adj^{(1)} ,\ldots,adj^{(k)} ,\ldots,adj^{(n)}$
    \item 其中经过第k次迭代,$adj^{(k)}[i,j]$ 的值等于从结点$v_i$ 到结点 $v_j$ 路径上所经过的结点序号不大于 k 的最短路径长度。
\end{itemize}
由于第 k 次迭代时已求得矩阵 $adj^{(k-1)}$ ,那么从结点 $v_i$
到 $v_j$ 中间结点的序号不大于 k 的最短路径有两种情况:
\begin{itemize}
    \item 一种是中间不经过结点 $v_k$ ,那么此时就有$adj^{(k)} [i,j] = adj^{(k-1)} [i,j]$
    \item 另中间经过结点 v k ,此时 $adj^{(k)} [i,j] < adj^{(k-1)} [i,j]$,
          那么这条由结点 $v_i$ 经过 $v_k$ 到结点 $v_j$ 的中间结点序号不大于k的最短路径由两段组成$adj^{(k)} [i,j] = adj^{(k-1)} [i,k] + adj^{(k-1)} [k,j]$
\end{itemize}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{dg19}
    \caption{Floyd算法示意图}
\end{figure}
代码：
\begin{cpp}
    Floyd(Graph & G,DIst** &D){
    int i,j,v;
    D = new Dist*[G.VerticesNum()];
    for(i = 0;i<G.VerticesNUm();i++)
    D[i] = new Dist[G.VerticesNum()];
    for(i = 0;i<G.VerticesNum();i++)
    {
    for(j=0;j<G.VerticesNum();j++)
    {
            if(i == j)
            {
                    D[i][j].length = 0;
                    D[i][j].pre = i;
                }
            else
                {
                    D[i][j].length = INFINITE;
                    D[i][j].pre = -1;
                }
        }
    for(v = 0;v<G.VerticesNum();v++)
    {
            for(Edge e = G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e))
            {
                    D[v][G.ToVertex(e)].length = G.Weight(e);
                    D[v][G.ToVertex(e)].pre = v;
                }
        }
    // 加入新节点后，更新那些边短的路径长度
    for(v = 0;v<G.VerticesNum();v++)
    for(i = 0;i<G.VerticesNum();i++)
    for(j = 0;j<G.VerticesNum();j++)
    if(D[i][j].length>(D[i][v].length+D[v][j].length)
    {
    D[i][j].length = D[i][v].length+D[v][j].length;
    D[i][j].pre = D[v][j].pre;
    }
    }
    }
\end{cpp}
Floyd算法的时间复杂度$\Theta(n^3)$
\subsection{最小生成树实现}
实现边和节点类。边的头文件：
\cppfile{code/offer/ex8/Edge.hpp}
边实现：
\cppfile{code/offer/ex8/Edge.cc}
节点类定义：
\cppfile{code/offer/ex8/Node.hpp}
节点类实现：
\cppfile{code/offer/ex8/Node.cc}
图的头文件：
\cppfile{code/offer/ex8/CMap.hpp}
图的类实现：
\cppfile{code/offer/ex8/CMap.cc}
测试函数：
\cppfile{code/offer/ex8/main.cpp}
\subsection{实现图的深度优先和广度优先算法}
\begin{example}[无向图的DFS和BFS]
    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=0.5\textwidth]{ex_bfs.pdf}
        \caption{无向图示意图}
    \end{figure}
    实现DFS遍历（A-B-C-E-F-D-G-H）和 BFS(A-B-D-C-F-G-H-E)
\end{example}
节点的类定义：
\cppfile{code/offer/dfs/Node.hpp}
节点的实现：
\cppfile{code/offer/dfs/Node.cc}
图的头文件：
\cppfile{code/offer/dfs/Graph.hpp}
图的实现：
\cppfile{code/offer/dfs/Graph.cc}
测试代码:
\cppfile{code/offer/dfs/main.cpp}

\subsection{二分图}
\begin{definition}[完全二分图]
    设G=(V,E)是一个无向图，如果定点V可以分割为两个互补相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个定点i和j分别属于这个不同的定点集合，则称G是一个二分图。二分图的等价定义：不含有含奇数条边的环（贿赂的长度均为偶数）的图。
\end{definition}
\begin{definition}[匹配]
    匹配是一个边的集合，其中任意两条边都没有公共顶点。
\end{definition}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{div_graph.pdf}
    \caption{匹配示意图}
    \label{fig:div_graph}

\end{figure}
\figref{fig:div_graph}中图2，1,4,5,7是匹配点，其它顶点为未匹配点,1-5,4-7为匹配边，其它边为非匹配边。
\begin{definition}[最大匹配]
    图中变数最多的匹配称为最大匹配。
\end{definition}
\begin{definition}[完美匹配]
    如果一个图的某个匹配中，素有的顶点都是匹配点，那么他就是一个完美匹配。完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边会和已经有的匹配边冲突）。但并非每个图都存在完美匹配。
\end{definition}
\begin{definition}[交替路]
    从一个未匹配点出发，经过非匹配边，匹配边，非匹配边形成的路径称为交替路。
\end{definition}
\begin{definition}[增广路]
    从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），这条路经称为增广路。
\end{definition}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{augument_path.pdf}
    \caption{交替路和增广路}
\end{figure}
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{argument_path_ex.pdf}
    \caption{增广路径例子}
\end{figure}
\begin{remark}[增广路的性质]
    \begin{enumerate}
        \item 有奇数条边。
        \item 起点在二分图的左半边，终点在右半边。
        \item 路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。）
        \item 整条路径上没有重复的点。
        \item    起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。）
        \item 路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。）
        \item 最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。（如图2所示，新的匹配就是所有蓝色的边，而所有红色的边则从原匹配中删除。则新的匹配数为3。
    \end{enumerate}
\end{remark}
\begin{definition}[最小覆盖]
    最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的最大匹配数；

    最小路径覆盖也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-二分图的最大匹配数；
\end{definition}
\begin{theorem}
    如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。
\end{theorem}
匈牙利算法过程示意图：
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{hungarian.pdf}
    \caption{匈牙利算法示意图（BFS）}
\end{figure}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{匈牙利算法.pdf}
    \caption{匈牙利算法}
\end{figure}
图2选中x1的第一个连接点(红线)，图3选中x2的第一个连接点y2,图3,x3选中y1发现x3的第一条x3-y1边被占据了，找出x3出发的交错路径。剩余的边x3-y1,x1-y4加到匹配中去。
\cppfile{code/offer/ex19/test.cc}
\subsection{二分图染色问题}
\begin{example}[二分图染色问题]
    对一个节点（白色），和它相邻的节点（黑色（不同颜色）），所有边两边的节点颜色不同则为二分图，否则不是。
    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=0.5\textwidth]{isdiv.pdf}
        \caption{染色例子}
    \end{figure}
\end{example}
\cppfile{code/arith/ex11/main.cpp}
整个代码以一个起点开头深搜，如果visited是初始化状态，设置他的状态，然后判断相邻节点状态和它是否相同，如果相同，则无法二分，否则，相邻节点被反色。以相邻节点为起点开始搜索，知道结束。
在代码中是否访问visited使用的是int，而不是bool数组。因为visited应该有三种状态，初始状态，设置状态，设置状态的相反状态。
\subsection{环的检测}
\textbf{无向图的环检测方法}
\begin{itemize}
    \item 拓扑排序：找入度为0的顶点，输出顶点，删除边。循环知道无顶点输出。如果输出所有的顶点，则拓扑排序，无环。否则不能拓扑排序，有环。
    \item DFS+回溯：回溯遍历，如果遇到之前访问过的节点，则图中有环。
    \item DFS+判断后退边：在遍历顶点的每一条边时，判断一下这个边的顶点是不是在栈中，如果在栈中说明之前已经访问过，这里再次访问，说明有环存在。
\end{itemize}
\textbf{无向图的检测方法}
\begin{example}[拓扑排序]
    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=0.5\textwidth]{topo.pdf}
        \caption{拓扑排序}
    \end{figure}
    \cppfile{code/arith/ex12/main.cpp}
\end{example}
\subsection{并查集}
并查集是一种树形结构，又叫不相交集合,保持了一组不像叫得动态集合，每个集合通过一个代表识别，代表即集合中的某个成员，通常选择根做这个代表。
并查集的三种主要操作：
Make\_Set(x):
建立一个新的集合，其唯一成员就是x，因此这个集合的代表也是x，并查集要求各集合是不相交的，因此要求x没有在其他集合中出现过。

Find\_Set(x):返回能代表x所在集合的节点，通常返回x所在集合的根节点。有递归和非递归两种方法，下面会有讲解。

Union(x, y):将包含x,y的动态集合合并为一个新的集合。合并两个集合的关键是找到两个集合的根节点，如果两个根节点相同则不用合并；如果不同，则需要合并。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{union_set.pdf}
    \caption{并查集}
\end{figure}
Union(x, y)时按秩合并：
合并时，如果两个集合的秩相同，任选一个根做为父节点，并增加其秩。
秩不同时，让较小秩的集合指向较大秩的集合，这时秩的大小不变。
秩和集合的数目是不一样的，秩表示节点高度的一个商界；集合的数目表示集合中节点的总数。
Find\_Set(x)路径压缩：在Find\_Set(x)中，是查找路径上的每个节点都直接指向根节点，这样下次再找根节点的时间复杂度会变成o(1)
